The Parameterized Complexity of s-Club with Triangle and Seed Constraints
Open Access
- 12 August 2023
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 67 (5) , 1050-1081
Abstract
The s-Club problem asks whether a given undirected graph 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 each edge of G[S] is contained in at least $$\ell $$ triangles in G[S], 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.
Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (EAGR (KO 3669/6-1))
This publication has 22 references indexed in Scilit:
- Finding clubs in graph classesDiscrete Applied Mathematics, 2014
- Seed-Centric Approaches for Community Detection in Complex Networks2014
- On clique relaxation models in network analysisEuropean Journal of Operational Research, 2013
- Finding large $k$ -clubs in undirected graphsComputing, 2012
- Identifying large robust network clusters via new compact formulations of maximum k-club problemsEuropean Journal of Operational Research, 2012
- Parameterized computational complexity of finding small-diameter subgraphsOptimization Letters, 2011
- On problems without polynomial kernelsJournal of Computer and System Sciences, 2009
- Novel Approaches for Analyzing Biological NetworksJournal of Combinatorial Optimization, 2005
- An exact algorithm for the maximum k-club problem in an undirected graphEuropean Journal of Operational Research, 2002
- Cliques, clubs and clansQuality & Quantity, 1979