Abstract
Finding cohesive subgroups is a fundamental task in network analysis. While the $s$-club model—requiring an induced subgraph to have diameter at most $s$—is well-studied, it often produces sparse or fragile clusters. This research explores the parameterized complexity of $s$-club variants that incorporate triangle-based density constraints and "seed" vertex requirements. The authors provide a complete complexity dichotomy, demonstrating that while the basic problem is Fixed-Parameter Tractable (FPT), most constrained variants are $W[1]$-hard, with specific exceptions that allow for efficient kernelization.
Introduction
In social and biological network analysis, researchers often seek "cohesive subgroups"—sets of nodes that are closely knit. A classic model for this is the $s$-club: a set of vertices $S$ where the distance between any two nodes in the induced subgraph is at most $s$. However, $s$-clubs frequently suffer from a "hub-and-spoke" problem, where a single central node can connect many otherwise distant nodes, resulting in a cluster that is sparse and fragile.
To address this, researchers have proposed two primary types of constraints:
- Triangle Constraints: Every vertex (or edge) must be part of at least $\ell$ triangles to ensure local density and redundancy.
- Seed Constraints: The cluster must contain a specific set of "seed" vertices $W$, representing known members of a community.
This paper investigates whether adding these practically motivated constraints makes the problem significantly harder to solve from a parameterized complexity perspective, specifically when the solution size $k$ is small.
Methodology
The authors employ parameterized complexity analysis, using the solution size $k$ as the primary parameter. Their methodology includes:
- Hardness Reductions: Proving $W[1]$-hardness by reducing from the Clique problem, suggesting these variants likely cannot be solved in $f(k) \cdot n^{O(1)}$ time.
- Turing Kernels: For tractable (FPT) cases, they develop "Turing kernels," showing the problem can be reduced to a set of smaller instances whose size depends only on $k$.
- Edge-$\ell$-triangle Modeling: They introduce a new property that is "closed under edge insertion." Unlike vertex-based models, adding a connection within a group in this model won't destroy its status as a valid cluster, making it more robust for real-world applications.
Complexity Results
The core contribution of this work is a complete complexity dichotomy for these variants. The research reveals that FPT results for $s$-clubs are remarkably "brittle." Adding almost any additional constraint—such as requiring a seed set that isn't a clique or requiring nodes to be in multiple triangles—immediately pushes the problem into $W[1]$-hardness.
Key findings include:
- The Power of the Clique Seed: If the seed set $W$ is a clique, the problem remains tractable. However, if $W$ contains even two non-adjacent vertices (for $s=2$), it becomes $W[1]$-hard.
- Edge vs. Vertex Triangles: The Edge-$\ell$-triangle constraint is not only superior for modeling but also more algorithmically well-behaved, remaining FPT for $\ell=1$ across all values of $s$. In contrast, the Vertex Triangle variant is only FPT for $\ell=1$ when $s \ge 4$.
- Kernelization: For FPT cases, the authors provide concrete kernel sizes, such as a $k^4$-vertex Turing kernel for Vertex Triangle $s$-Club when $s=4$.
Discussion and Future Work
While the study focuses on solution size $k$, the authors suggest that future work should examine structural parameters like treewidth or degeneracy, which might yield FPT results where $k$ failed. The "Seeded" variant is particularly promising for practical applications when the seed set is of constant size.
Although the results are primarily theoretical, the authors express optimism that the $s=2$ case can be solved efficiently in practice on sparse, real-world graphs using branch-and-bound techniques. Future research may also extend these findings to other robust models, such as $t$-hereditary $s$-clubs or $s$-plexes with seeds.
Summary updated