TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 16.02.2012



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

On Structural Parameterizations of 2-Club

Sepp Hartung (TU Berlin)

Given an undirected graph G and an integer l the 2-Club problem is to decide whether there is an induced subgraph with at least l vertices in G that has diameter at most two. The problem is already known to be fixed-parameter tractable with respect to l and it admits a polynomial-size turing kernel (Schäfer et al. Opt. Letters, 2011). We provide a systematic study of structural parameterizations of 2-Club. Specifically, we give fixed-parameter algorithms with respect to the parameters vertex cover, distance to cograph, and size of a cluster editing set. We complement these positive results by showing NP-hardness for 2-Club on split graphs, graphs that become bipartite by deleting one vertex, graphs that can be covered by three cliques, and on graphs with domination number two and diameter three. Furthermore, we show that 2-Club is W[1]-hard with respect to the parameter h-index. We also investigate kernelization algorithms and there limits of application. We show a linear size kernel for the parameter feedback edge set and a quadratic kernel for the parameter size of a cluster editing set. Finally, under some reasonable complexity theoretical assumptions, we show that 2-Club does not admit a polynomial-size kernel with respect to the parameter vertex cover.

16.02.2012 16:15
Sepp Hartung
FR 6510

* Language is depending on the audience.

Back to the research colloquium site.



Schnellnavigation zur Seite über Nummerneingabe