direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras