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_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_4: Assuming that NP @math @math BPTIME( @math ), we show that graph min-bisection, dense @math -subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values.
summary: Feige and Seltser @cite_9 showed the densest @math -subgraph problem is @math -complete when restricted to bipartite graphs of maximum degree 3, by a reduction from max-clique. This reduction does not produce a hardness of approximation result for DkS. In fact, they showed that if a graph contains a @math -clique, a subgraph with @math vertices and @math edges can be found in subexponential time. Khot @cite_4 proved there can be no PTAS for the densest @math -subgraph problem, under a standard complexity assumption.