Finding connected k -subgraphs with high density

Given an edge-weighted 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 weighted density is at least a factor Ω ( max ⁡ { 1 / k, k 2 / n 2 } ) of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where max ⁡ { 1 / k, k 2 / n 2 } ≥ n − 2 / 3 implies an O ( n 2 / 3 ) -approximation ratio. We obtain improved O ( n 2 / 5 ) -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give O ( n log ⁡ n ) -approximation for the problem on general weighted interval graphs.

Authors

• Xujin Chen
• Xiaodong Hu
• Changjun Wang

Keywords

• Densest k-subgraphs
• Heaviest k-subgraphs
• Connectivity
• Approximation algorithms
• Interval graphs