On structural parameterizations for the 2-club problem

Sepp Hartung, Christian Komusiewicz, André Nichterlein, Ondrej Suchý

TL;DR

This paper investigates the computational complexity of the 2-Club problem, which asks for a large subgraph with a diameter of at most two. The authors provide a comprehensive classification of its complexity with respect to various structural graph parameters, establishing tight boundaries between tractable and intractable cases. This work is crucial for understanding how graph properties influence the difficulty of finding cohesive subnetworks in real-world networks.

What Problem Does This Paper Address?

Identifying cohesive subnetworks is a fundamental task in analyzing complex networks, such as social or biological ones. A common way to define cohesiveness is through graph properties like cliques (diameter 1). However, this can be too restrictive. The 2-Club problem offers a more relaxed definition: finding a vertex set whose induced subgraph has a diameter of at most two. This problem is known to be NP-hard.

The authors aim to understand how the complexity of the 2-Club problem changes when considering different "structural parameters" of the input graph. These parameters are numerical properties of a graph (like its maximum degree or degeneracy) that can help classify its structure. The goal is to determine which parameters make the problem computationally easier (fixed-parameter tractable, FPT) and which keep it hard (NP-hard even for small parameter values). This systematic classification is essential for developing efficient algorithms for real-world applications where graphs often possess specific structural characteristics.

Methods

The paper employs two main frameworks: NP-hardness reductions and parameterized complexity.

  • NP-Hardness Reductions: The authors construct new graphs based on existing NP-hard problems (like CLIQUE and MAXIMUM 2-SAT) to demonstrate that the 2-Club problem remains NP-hard even when restricted to graphs with specific structural properties (e.g., graphs that are "almost bipartite" or have a small clique cover number).
  • Parameterized Complexity: This framework analyzes the complexity of a problem with respect to a parameter k.
  • Fixed-Parameter Tractability (FPT): Algorithms with running times like $f(k) \cdot |I|^{O(1)}$, where $|I|$ is the input size.
  • XP (Cross-Parametrization): Algorithms with running times like $|I|^{f(k)}$.
  • W[1]-hardness: A class of problems believed to be harder than FPT, suggesting that no $f(k) \cdot |I|^{O(1)}$ algorithm exists.
  • Kernelization: Techniques to reduce the instance size polynomially while preserving the solution, aiming for polynomial kernels.

The paper presents both positive (FPT algorithms) and negative (W[1]-hardness, NP-hardness for constant parameters) results for various parameters.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tight Boundaries: The paper establishes sharp boundaries for the 2-Club problem's complexity across a hierarchy of structural parameters. This means they often show that a parameter makes the problem FPT, but a slightly "weaker" parameter keeps it NP-hard, highlighting the sensitivity of the problem to structural properties.
  • "Almost Bipartite" is Hard: Surprisingly, 2-Club is NP-hard even on graphs that become bipartite by deleting just one vertex. This is notable because 2-Club is polynomial-time solvable on bipartite graphs themselves.
  • h-index vs. Degeneracy: While the h-index is a relevant parameter for social networks, the paper shows 2-Club is W[1]-hard for the h-index but NP-hard for constant degeneracy. This suggests that even though degeneracy is related to the h-index, it's a stronger structural property that preserves hardness.
  • Distance to Cographs/Cluster Graphs: The paper provides FPT algorithms for 2-Club parameterized by the distance to cographs and cluster graphs. These are rare examples of structural parameters (unrelated to treewidth) that admit FPT algorithms, offering a more positive outlook for these specific graph classes.
  • Parameter Hierarchy Matters: The work emphasizes the importance of understanding how parameters relate to each other (as visualized in their Figure 1). This helps in identifying the most "powerful" parameters for tractability.

Key Results

  • NP-Hardness Results:
    • 2-Club is NP-hard on graphs that become bipartite by deleting one vertex.
  • 2-Club is NP-hard on graphs with clique cover number three and diameter three.
  • 2-Club is NP-hard on graphs with domination number two and diameter three.
  • 2-Club is NP-hard even for constant degeneracy.
  • Parameterized Tractability Results:
    • 2-Club is FPT with respect to the h-index k with a running time of $O(2^{k^2} \cdot n^{2k} \cdot n^2m)$.
  • 2-Club is FPT with respect to distance to cographs in $O(2^k \cdot 8^{2^k} \cdot n^4)$ time.
  • 2-Club is FPT with respect to distance to cluster graphs in $O(2^k \cdot 3^{2^k} \cdot nm)$ time.
  • Parameterized Hardness Results:
    • 2-Club is W[1]-hard when parameterized by the h-index.
  • 2-Club is NP-hard on graphs with constant degeneracy.

Limitations and Future Work

  • Open Parameterizations: The paper identifies several open questions, including whether 2-Club is FPT or even in XP when parameterized by distance to interval graphs or distance to 2-club cluster graphs.
  • Kernelization: It remains open whether polynomial kernels exist for parameters like distance to clique.
  • Algorithm Improvement: For existing FPT algorithms, improving running times (e.g., for distance to clique or vertex cover) is a direction for future work.
  • Generalization: The authors suggest exploring whether these results extend to the 3-Club problem or the related 2-Clique problem.
  • Combined Parameters: Investigating the complexity of 2-Club when parameterized by combinations of parameters (e.g., h-index and constant degeneracy) is also an open area.

Summary updated

Abstract

The NP-hard 2-Club problem is, given an undirected graph G=(V,E) and l\in N, to decide whether there is a vertex set S\subseteq V of size at least l such that the induced subgraph G[S] has diameter at most two. We make progress towards a systematic classification of the complexity of 2-Club with respect to a hierarchy of prominent structural graph parameters. First, we present the following tight NP-hardness results: 2-Club is NP-hard on graphs that become bipartite by deleting one vertex, on graphs that can be covered by three cliques, and on graphs with domination number two and diameter three. Then, we consider the parameter h-index of the input graph. This parameter is motivated by real-world instances and the fact that 2-Club is fixed-parameter tractable with respect to the larger parameter maximum degree. We present an algorithm that solves 2-Club in |V|^{f(k)} time with k being the h-index. By showing W[1]-hardness for this parameter, we provide evidence that the above algorithm cannot be improved to a fixed-parameter algorithm. Furthermore, the reduction used for this hardness result can be modified to show that 2-Club is NP-hard if the input graph has constant degeneracy. Finally, we show that 2-Club is fixed-parameter tractable with respect to distance to cographs.
BibTeX
@article{hartung2015structural,
  author = {Sepp Hartung and Christian Komusiewicz and André Nichterlein and Ondrej Suchý},
  title = {{On structural parameterizations for the 2-club problem}},
  journal = {Discret. Appl. Math.},
  year = {2015},
  doi = {10.1016/j.dam.2014.11.026},
}
Figure