5
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ The problem is not in NP, as it is not even a decision problem. It is in TFNP. $\endgroup$ Sep 7 '21 at 12:18
  • 2
    $\begingroup$ I wanted to remark that P and NP are defined as collections of decision problems, not search problems. So you should be asking whether this problem is in FP i.e. the set of search problems solvable in polynomial time. $\endgroup$ Sep 7 '21 at 12:20
  • 1
    $\begingroup$ My bad, have amended the question. $\endgroup$
    – ckamath
    Sep 7 '21 at 14:34
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.