{"ID":2845627,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03157","arxiv_id":"2511.03157","title":"A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems","abstract":"A graph with $n$ vertices is an $f(\\cdot)$-dense graph if it has at least $f(n)$ edges, $f(\\cdot)$ being a well-defined function. The notion $f(\\cdot)$-dense graph encompasses various clique models like $γ$-quasi cliques, $k$-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. However, the $f(\\cdot)$-dense graph may be disconnected or weakly connected. To conquer this, we study the problem of finding the largest $f(\\cdot)$-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(\\cdot)$ functions show our algorithm outperforms the MIP solver and pure branch-and-bound, solving nearly twice as many instances optimally within one hour.","short_abstract":"A graph with $n$ vertices is an $f(\\cdot)$-dense graph if it has at least $f(n)$ edges, $f(\\cdot)$ being a well-defined function. The notion $f(\\cdot)$-dense graph encompasses various clique models like $γ$-quasi cliques, $k$-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. Ho...","url_abs":"https://arxiv.org/abs/2511.03157","url_pdf":"https://arxiv.org/pdf/2511.03157v2","authors":"[\"Yi Zhou\",\"Chunyu Luo\",\"Zhengren Wang\",\"Zhang-Hua Fu\"]","published":"2025-11-05T03:35:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}