Computational complexity of Turán-type problems

Question

According to Turán's theorem (with $r=n/2$), any graph $G$ with $n$ vertices and at least $n(n-2)/2$ edges must contain a clique of size $n/2+1$. My question is: how hard is it to find this clique?$^*$ The problem is clearly in $\mathbf{FNP}$, and in fact in $\mathbf{TFNP}$. Moreover, by looking at the original proof of existence (first proof given here), it seems to be solvable by polynomial-time algorithm which recursively computes the clique (i.e. the problem is in $\mathbf{FP}$). Am I missing something here?

$^*$The corresponding problem for $r=2$ (i.e., Mantel's theorem) is easy since we can enumerate over all triples of vertices in $G$.

Answer 1

Since $r$ has to be an integer, I assume $n$ is even. I’m pretty sure the discussion below works for $n$ odd as well, if you decide whether you want $r=(n+1)/2$ or $r=(n-1)/2$ and adjust the bound according to the statement of Turán’s theorem.

I find it easier to express the problem in terms of the complement of your graph. Then it becomes: given a graph $G$ on $n$ vertices with at most $n/2$ edges, find an independent set of size $n/2+1$.

First, there is an off-by-one error: if $G$ consists of $n/2$ disjoint edges, it does not have any independent set of size $n/2+1$. Indeed, the statement of Turán’s theorem as given by your link requires $G$ to have strictly more than $n(n-2)/2$ edges, so in terms of the complement, the correct problem is: given a graph with less than $n/2$ edges, find an independent set of size $n/2+1$.

This can be done trivially by the following polynomial-time algorithm: pick one vertex in each connected component of $G$.

Indeed, since a component with $m$ vertices has at least $m-1$ edges, the number of edges in a graph with $n$ vertices and $c$ components is at least $n-c$. Thus, a graph with $\le n/2-1$ edges has $\ge n/2+1$ components.