The complexity of detecting fixed-density clusters

We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let γ:N→Q+γ:N→Q+ be any density function, i.e., γγ is computable in polynomial time and satisfies γ(k)⩽k-1γ(k)⩽k-1 for all k∈Nk∈N. Then γγ-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k   vertices that has average degree at least γ(k)γ(k). For γ(k)=k-1γ(k)=k-1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for γ(k)=2γ(k)=2. We ask for the possible functions γγ such that γγ-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: γγ CLUSTER is NP-complete if γ=2+Ω(1/k1-ε)γ=2+Ω(1/k1-ε) for some ε>0ε>0 and has a polynomial-time algorithm for γ=2+O(1/k)γ=2+O(1/k). The algorithm also shows that for γ=2+O(1/k1-o(1))γ=2+O(1/k1-o(1)), γγ-CLUSTER is solvable in subexponential time 2no(1)2no(1).