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_12: The k-f(k) dense subgraph problem ((k, f(k))-DSP) asks whether there is a k-vertex subgraph of a given graph G which has at least f(k) edges. When f(k)=k(k - 1) 2, (k,f(k))-DSP is equivalent to the well-known k-clique problem. The main purpose of this paper is to discuss the problem of finding slightly dense subgraphs. Note that f(k) is about k2 for the k-clique problem. It is shown that (k,f(k))-DSP remains NP-complete for f(k)= Θ(k1+e) where e may be any constant such that 0 < e < 1. It is also NP-complete for "relatively" slightly-dense subgraphs, i.e., (k, f(k))-DSP is NP-complete for f(k)= ek2 υ2(1 +O(υe-1)), where υ is the number of G's vertices and e is the number of G's edges. This condition is quite tight because the answer to (k, f(k))-DSP is always yes for f(k)= ek2 υ2(1 -(υ- k) (υk- k)) that is the average number of edges in a subgraph of k vertices. Also, we show that the hardness of (k, f(k))-DSP remains for regular graphs: (k, f(k))-DSP is NP-complete for Θ(υe1)-regular graphs if f(k)= Θ(k1-e2) for any 0 < e1, e2 < 1.
  @cite_11: We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense” instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By dense graphs we mean graphs with minimum degree Ω(n), although our algorithms solve most of these problems so long as the average degree is Ω(n). Denseness for non-graph problems is defined similarly. The unified framework begins with the idea of exhaustive sampling: picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain smooth integer programs where the objective function and the constraints are “dense” polynomials of constant degree.
summary: Arora, Karger, and Karpinski @cite_11 gave a PTAS for the special case @math and @math . Asahiro, Hassin, and Iwama @cite_12 showed that the problem is still @math -complete in very sparse graphs.