{'fraction_non_alphanumeric': 0.050960735171261484, 'fraction_numerical': 0.009189640768588136, 'mean_word_length': 4.650943396226415, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

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 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 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) search tree algorithm [Schafer et al., Optim. Lett. 2012] cannot be improved and that, unless NP⊆coNP/poly, there is no polynomial 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 substantially outperforms previous implementations.