Abstract
This paper maps the computational landscape of the 2-Club problem—finding the largest subnetwork with a diameter of at most two—through the lens of structural graph parameters. By identifying sharp boundaries between tractability and NP-hardness, the authors prove that while the problem remains difficult even for very "simple" graphs (like those nearly bipartite), it becomes solvable when the graph is close to being a cograph or has a bounded $h$-index. This work provides a comprehensive classification of the problem's complexity across a hierarchy of graph properties.
Introduction
In network analysis, identifying cohesive subnetworks is a fundamental task. While a clique (where every pair of nodes is adjacent) is the traditional gold standard for cohesion, it is often too restrictive for real-world biological or social data. The $s$-club is a popular relaxation: it is a set of vertices that induces a subgraph with a diameter of at most $s$.
This paper focuses on the 2-Club problem ($s=2$), which is known to be NP-hard. While previous research established its tractability when parameterized by solution size or treewidth, this study explores structural parameterizations. The central question is: "If the input graph has a specific shape or property, does the problem become easier?"
The Structural Landscape of 2-Club
The authors employ the toolkit of parameterized complexity analysis to categorize various graph properties into a hierarchy. This hierarchy includes parameters such as vertex cover, $h$-index, degeneracy, and distance to specific graph classes (e.g., cographs, bipartite graphs).
As shown in the figure above, the authors identify clear regions of tractability. The problem is fixed-parameter tractable (FPT) for parameters like distance to clique and distance to cograph, but it quickly becomes NP-hard or W[1]-hard as the parameters become more general (e.g., distance to bipartite or $h$-index).
Key Insights and Methodology
The Non-Hereditary Challenge
Unlike cliques, the 2-club property is not hereditary. Deleting a vertex from a 2-club can cause the diameter of the remaining subgraph to increase beyond two. This characteristic makes standard algorithmic techniques, such as simple pruning, difficult to apply and necessitates more sophisticated structural analysis.
Hardness Reductions
The authors demonstrate "deceptive simplicity" in graph structures. A significant finding is that 2-Club remains NP-hard even for graphs with distance one to bipartite. This means that even if removing a single vertex makes the graph bipartite (a class where 2-Club is easy), the problem remains fundamentally difficult. Similarly, the problem is NP-hard for graphs with a domination number of 2 or constant degeneracy.
The $h$-index Boundary
The paper identifies the $h$-index (the largest $k$ such that $k$ vertices have degree at least $k$) as a critical threshold. While 2-Club is FPT for the maximum degree, it is W[1]-hard for the $h$-index. Since real-world social networks often follow power-law distributions with a few high-degree hubs, this result suggests that these hubs are precisely what drive the computational difficulty of the problem.
New Algorithmic Results
The study introduces several new algorithms to navigate this landscape:
- FPT Algorithm for Distance to Cographs: Using dynamic programming on cotrees, the authors show the problem is solvable in $2^{O(2^k)} \cdot n^{O(1)}$ time, where $k$ is the number of vertices to delete to reach a cograph.
- XP Algorithm for $h$-index: The problem is solvable in $|V|^{f(k)}$ time, where $k$ is the $h$-index, using a combination of branching and "cleaning" steps to remove nodes that cannot be part of a diameter-2 solution.
Practical Implications and Datasets
To justify the focus on specific structural parameters, the authors analyzed the DBLP coauthor network (over 715,000 vertices). They found that structural parameters like $h$-index (208) and average degree (7) are significantly smaller than the maximum degree (804). This empirical evidence supports the theoretical pursuit of algorithms parameterized by these smaller values, even if the current algorithms have high exponential dependencies.
Conclusion and Future Work
This research provides a rigorous map of the 2-Club problem's complexity. While it identifies new FPT results, it also highlights the inherent difficulty of the problem even under strict structural constraints. Future work may involve investigating the distance to interval graphs, seeking polynomial kernels for the "distance to clique" parameter, and extending these structural results to the 3-Club problem.
Summary updated