text: We consider two optimization problems related to finding dense subgraphs. The densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems are related to the well-known densest k-subgraph problem (DkS), which is to find the densest subgraph on exactly k vertices. We show that DalkS can be approximated efficiently, while DamkS is nearly as hard to approximate as the densest k-subgraph problem.
  @cite_1: Given a graph G=(V,E), a weight function w: E?R+, and a parameter k, we consider the problem of finding a subset U?V of size k that maximizes:Max-Vertex Coverk: the weight of edges incident with vertices in U,Max-Dense Subgraphk: the weight of edges in the subgraph induced by U,Max-Cutk: the weight of edges cut by the partition (U,V ),Max-Uncutk: the weight of edges not cut by the partition (U,V ).For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80 of the edges.
  @cite_9: Given an n-vertex graph G and a parameter k, we are to find a k-vertex subgraph with the maximum number of edges. This problem is NP-hard. We show that the problem remains NP-hard even when the maximum degree in G is three. When G contains a k-clique, we give an algorithm that for any e sub sub<) e). We study the applicability of semidefinite programming for approximating the dense k-subgraph problem. Our main result in this respect is negative, showing that for k @ n1 3, semidefinite programs fail to distinguish between graphs that contain k-cliques and graphs in which the densest k-vertex subgraph has average degree below logn.
  @cite_10: Given an n-vertex graph with nonnegative edge weights and a positive integer k?n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1 2+n 2k)2?O(n?1 3)?R?(1 2+n 2k)2+O(1 n) for k in the range n 3?k?n and 2(n k?1)?O(1 k)?R?2(n k?1)+O(n k2) for k
  @cite_7: This paper considers the problem of computing the dense k -vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(n δ ) , for some δ < 1 3 .
summary: We will briefly survey a few results on the complexity of the densest @math -subgraph problem. The best approximation algorithm known for the general problem (when @math is specified as part of the input) is the algorithm of Feige, Peleg, and Kortsarz @cite_7 , which has ratio @math for some @math . For any particular value of @math , the greedy algorithm of @cite_10 gives the ratio @math . Algorithms based on linear programming and semidefinite programming have produced approximation ratios better than @math for certain values of @math , but have not improved the approximation ratio of @math for the general case @cite_9 @cite_1 .