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,k2/n2}) of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where max⁡{1/k,k2/n2}≥n−2/3 implies an O(n2/3)-approximation ratio. We obtain improved O(n2/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(nlog⁡n)-approximation for the problem on general weighted interval graphs.