Finding Connected Dense k-Subgraphs

2015/01/29 by Xujin Chen, Chen, Xujin, Hu, Xiaodong +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1501.07348

openalex publication_date 2015/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a connected graph G on n vertices and a positive integer k≤ n, a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its density is at least a factor Ω(max\n^-2/5,k²/n²\) of the density of the densest k-subgraph in G (which is not necessarily connected). These particularly provide the first non-trivial approximations for the densest connected k-subgraph problem on general graphs.

Citations

• Combinatorial optimization: networks and matroids

Related

• Planted Models for the Densest k-Subgraph Problem
• Detecting High Log-Densities -- an O(n¹/4) Approximation for Densest k-Subgraph
• Finding large and small dense subgraphs
• A Local Algorithm for Finding Dense Subgraphs
• The Dense k Subgraph problem