2025/11/05 by Zhou, Yi, Luo, Chunyu, Wang, Zhengren +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.03157
A graph with n vertices is an f(⋅)-dense graph if it has at least f(n) edges, f(⋅) being a well-defined function. The notion f(⋅)-dense graph encompasses various clique models like γ-quasi cliques, k-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. However, the f(⋅)-dense graph may be disconnected or weakly connected. To conquer this, we study the problem of finding the largest f(⋅)-dense subgraph with a diameter of at most two in the paper. Specifically, we present a decomposition-based branch-and-bound algorithm to optimally solve this problem. The key feature of the algorithm is a decomposition framework that breaks the graph into n smaller subgraphs, allowing independent searches in each subgraph. We also introduce decomposition strategies including degeneracy and two-hop degeneracy orderings, alongside a branch-and-bound algorithm with a novel sorting-based upper bound to solve each subproblem. Worst-case complexity for each component is provided. Empirical results on 139 real-world graphs under two f(⋅) functions show our algorithm outperforms the MIP solver and pure branch-and-bound, solving nearly twice as many instances optimally within one hour.