On Choosing a Dense Subgraph (Extended Abstract)

This paper concerns the problem of computing the densest k-vertex subgraph of a given graph, namely, the subgraph with the most edges, or with the highest edges-to-vertices ratio. A sequence of approximation algorithms is developed for the problem, with each step yielding a better ratio at the cost of a more complicated solution. The approximation ratio of our final algorithm is O/spl tilde/(n/sup 0. 3885/). We also present a method for converting an approximation algorithm for an unweighted graph problem (from a specific class of maximization problems) into one for the corresponding weighted problem, and apply it to the densest subgraph problem. >

Authors

• Guy Kortsarz
• David Peleg

Keywords

• Approximation algorithms
• Costs
• Density measurement
• Mathematics
• Computer science
• Engineering profession
• Polynomials
• Topology
• Dense Subgraphs
• Estimation Algorithm
• Class Of Problems
• Maximization Problem
• Algorithm For Problem
• Approximate Ratio
• Rest Of The Paper
• General Case
• Feasible Set
• Maximum Weight
• Vertices
• Ratio Of Cases
• Binary Search
• Neighboring Vertices
• Induced Subgraph
• Proof Of Claim
• Expansion Properties
• Simple Lemma