Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

Details Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

2010-01-17

arxiv.org/abs/1001.2891v1

Computer Science

Data Structures and Algorithms

23 pages

Scientific paper

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n^(1/3-epsilon) for some specific epsilon > 0 (estimated at around 1/60). We present an algorithm that for every epsilon > 0 approximates the Densest k-Subgraph problem within a ratio of n^(1/4+epsilon) in time n^O(1/epsilon). In particular, our algorithm achieves an approximation ratio of O(n^1/4) in time n^O(log n). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from graphs with planted dense subgraphs. The approximation ratio we achieve for the general case matches the distinguishing ratio we obtain for this planted problem. At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. Our algorithm is based on the following principle. We say that a graph G(V,E) has log-density alpha if its average degree is Theta(|V|^alpha). The algorithmic core of our result is a family of algorithms that output k-subgraphs of nontrivial density whenever the log-density of the densest k-subgraph is larger than the log-density of the host graph.

Affiliated with

Also associated with

No associations

Rating

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455693