TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 08.12.2011



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

The Parameterized Complexity of Finding mu-Cliques - Preliminary Results

Manuel Sorge (TU Berlin)

Finding cliques of given minimum size in graphs is an extensively studied and practically relevant task. The concept of cliques, however, has also received criticism for being overly restrictive. In social networks, for example, cliques represent communities, but it is intuitive that subgraphs with only few missing edges represent sought-after communities, too. Thus, relaxations have been introduced, one of them being "mu-cliques". The density of a (simple) graph is the ratio of the number of edges it contains to the maximum number of edges it can contain. A mu-clique is a graph with density at least mu. Finding mu-cliques of given minimum size is NP-hard as well as finding cliques.

We present preliminary parameterized tractability and hardness results for the task "mu-CLIQUE" of finding a mu-clique of size at least k in a graph on n vertices. In particular, we note that mu-CLIQUE is W[1]-hard with respect to both the parameter n - k and the combined parameter k and degeneracy---which is a measure of sparseness. On the positive side, we note that mu-CLIQUE is fixed-parameter tractable with respect to each of the parameters maximum degree, h-index, and the combined parameter degeneracy and c-isolation. Here, c-isolation means that each vertex in the sought mu-clique has at most c neighbors in the rest of the graph. We briefly discuss interesting open questions and our ongoing research for mu-CLIQUE.

08.12.2011 16:15
Manuel Sorge
FR 6510

* Language is depending on the audience.

Back to the research colloquium site.



Schnellnavigation zur Seite über Nummerneingabe