Introduction
In network science, identifying dense subgraphs is a fundamental task for uncovering community structures in social, biological, and technological networks. While the "clique" (a subgraph where every pair of vertices is connected) is the most restrictive model, real-world data often contains noise or missing links. The Maximum $k$-plex Problem (MKP) offers a more flexible alternative: in a $k$-plex, each vertex is allowed to miss up to $k-1$ connections within the group.
Solving the MKP is NP-hard. State-of-the-art exact solvers typically employ a Branch-and-Bound (BnB) framework. The efficiency of BnB relies heavily on the quality of its upper bounds—mathematical estimates used to prune search branches that cannot yield a better solution than the current best. This paper introduces two novel upper bounds, RelaxGCB and RelaxPUB, designed to significantly tighten these estimates and accelerate the search process.
Methodology: RelaxGCB and RelaxPUB
The researchers proposed two primary strategies to improve pruning efficiency:
1. RelaxGCB: Leveraging the h-index Analogy
Traditional bounds often use graph coloring to identify independent sets. The authors enhance this with TISUB (Tighter Independent Set Upper Bound). Inspired by the academic h-index, TISUB calculates a bound for each set by considering the "budget" of non-neighbors each vertex can afford. A vertex $v$ can only belong to a $k$-plex if it has enough connectivity to the existing partial solution. By identifying the maximum number $i$ such that at least $i$ vertices in a set have a budget of at least $i$, the algorithm produces a much tighter bound.
2. RelaxPUB: A Hybrid Complementary Approach
The authors observed that coloring-based bounds (GCB) and partition-based bounds (PUB) excel in different scenarios. GCB focuses on internal connectivity, while PUB focuses on connectivity relative to the current partial solution.
RelaxPUB dynamically selects the best method at each step using a "dise" metric. This hybrid strategy ensures that the solver remains efficient regardless of the local graph structure encountered during the search.
Experimental Evaluation and Results
The new bounds were integrated into four leading MKP solvers: Maplex, kPlexS, DiseMKP, and KPLEX. Testing was conducted on 80 dense DIMACS graphs and 139 large-scale real-world graphs across $k$ values ranging from 2 to 15.
The results demonstrate that the new bounds reduce search tree sizes by several orders of magnitude. Instances that previously required hundreds of seconds were often solved in under a second. Furthermore, the RelaxPUB-based algorithms proved remarkably robust, solving many "unsolvable" instances that timed out for baseline solvers.
Conclusion
By introducing tighter upper bounds through the h-index inspired TISUB and a hybrid selection strategy, this work significantly advances the state-of-the-art in exact MKP solving. Future research may extend these relaxation techniques to other clique-related problems, such as $k$-cores or $s$-bundles, further broadening the tools available for complex network analysis.
Summary updated