The Parameterized Complexity of s-Club with Triangle and Seed Constraints

Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer

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:

  1. Triangle Constraints: Every vertex (or edge) must be part of at least $\ell$ triangles to ensure local density and redundancy.
  2. 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.

Table 1: Complexity dichotomy for s-club variants with triangle and seed constraints.

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

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},
}
Figure