The Parameterized Complexity of s-Club with Triangle and Seed Constraints
Lists
Only you see this
Abstract
The s-Club problem asks, for a given undirected graph G, whether G contains a vertex set S of size at least k such that G[S], the subgraph of G induced by S, has diameter at most s. We consider variants of s-Club where one additionally demands that each vertex of G[S] is contained in at least \(\ell \) triangles in G[S], that G[S] contains a spanning subgraph \(G'\) such that each edge of \(E(G')\) is contained in at least \(\ell \) triangles in \(G'\), or that S contains a given set W of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size k, making them significantly harder than the unconstrained s-Club problem. On the positive side, we obtain some FPT algorithms for the case when \(\ell =1\) and for the case when G[W], the graph induced by the set of seed vertices, is a clique.
BibTeX
@article{garvardt2023parameterized,
author = {Jaroslav Garvardt and Christian Komusiewicz and Frank Sommer},
title = {{The Parameterized Complexity of s-Club with Triangle and Seed Constraints}},
journal = {Theory Comput. Syst.},
year = {2023},
doi = {10.1007/s00224-023-10135-x},
}