Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00352
Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
Vol. 19, no. 1, pp. 155-190, 2015. Regular paper.
Abstract Given an undirected graph G=(V,E) and an integer l ≥ 1, the NP-hard  2-CLUB problem asks for a vertex set S ⊆ V of size at least l such that the subgraph induced by S has diameter at most two. In this work, we extend previous parameterized complexity studies for  2-CLUB. On the positive side, we give polynomial-size problem kernels for the parameters feedback edge set size of G and size of a cluster editing set of G and present a direct combinatorial algorithm for the parameter treewidth of G. On the negative side, we first show that unless NP ⊆ coNP/poly, 2-CLUB does not admit a polynomial-size problem kernel with respect to the size of a vertex cover of G. Next, we show that, under the strong exponential time hypothesis, a previous O(2|V|−l·|V||E|)-time search tree algorithm [Schäfer et al., Optim. Lett. 2012] cannot be improved and that, unless NP ⊆ coNP/poly, there is no polynomial-size problem kernel for the dual parameter |V|−l. Finally, we show that, in spite of this lower bound, the search tree algorithm for the dual parameter |V|−l can be tuned into an efficient exact algorithm for 2-CLUB that outperforms previous implementations.
Submitted: July 2013.
Reviewed: May 2014.
Revised: August 2014.
Accepted: February 2015.
Final: February 2015.
Published: March 2015.
Communicated by Petra Mutzel
article (PDF)
BibTeX