<p>Since <span class="math-container">$r$</span> has to be an integer, I assume <span class="math-container">$n$</span> is even. I’m pretty sure the discussion below works for <span class="math-container">$n$</span> odd as well, if you decide whether you want <span class="math-container">$r=(n+1)/2$</span> or <span class="math-container">$r=(n-1)/2$</span> and adjust the bound according to the statement of Turán’s theorem.</p>
<p>I find it easier to express the problem in terms of the complement of your graph. Then it becomes: given a graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices with at most <span class="math-container">$n/2$</span> edges, find an independent set of size <span class="math-container">$n/2+1$</span>.</p>
<p>First, there is an off-by-one error: if <span class="math-container">$G$</span> consists of <span class="math-container">$n/2$</span> disjoint edges, it does not <em>have</em> any independent set of size <span class="math-container">$n/2+1$</span>. Indeed, the statement of Turán’s theorem as given by your link requires <span class="math-container">$G$</span> to have <em>strictly more</em> than <span class="math-container">$n(n-2)/2$</span> edges, so in terms of the complement, the correct problem is: given a graph with less than <span class="math-container">$n/2$</span> edges, find an independent set of size <span class="math-container">$n/2+1$</span>.</p>
<p>This can be done trivially by the following polynomial-time algorithm: pick one vertex in each connected component of <span class="math-container">$G$</span>.</p>
<p>Indeed, since a component with <span class="math-container">$m$</span> vertices has at least <span class="math-container">$m-1$</span> edges, the number of edges in a graph with <span class="math-container">$n$</span> vertices and <span class="math-container">$c$</span> components is at least <span class="math-container">$n-c$</span>. Thus, a graph with <span class="math-container">$\le n/2-1$</span> edges has <span class="math-container">$\ge n/2+1$</span> components.</p>

CC BY-SA 4.0
2021-09-07T14:48:17.077Z
2021-09-07T14:48:17.077Z
Emil Jeřábek
<p>According to <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem" rel="nofollow noreferrer">Turán's theorem</a> (with <span class="math-container">$r=n/2$</span>), any graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> vertices and at least <span class="math-container">$n(n-2)/2$</span> edges must contain a clique of size <span class="math-container">$n/2+1$</span>. My question is: how hard is it to <em>find</em> this clique?<span class="math-container">$^*$</span> The problem is clearly in <a href="https://en.wikipedia.org/wiki/FNP_(complexity)" rel="nofollow noreferrer"><span class="math-container">$\mathbf{FNP}$</span></a>, and in fact in <a href="https://en.wikipedia.org/wiki/TFNP" rel="nofollow noreferrer"><span class="math-container">$\mathbf{TFNP}$</span></a>. Moreover, by looking at the original proof of existence (first proof given <a href="https://link.springer.com/chapter/10.1007%2F978-3-662-57265-8_41" rel="nofollow noreferrer">here</a>), it seems to be solvable by polynomial-time algorithm which recursively computes the clique (i.e. the problem is in <a href="https://en.wikipedia.org/wiki/FP_(complexity)" rel="nofollow noreferrer"><span class="math-container">$\mathbf{FP}$</span></a>). Am I missing something here?</p>
<p><span class="math-container">$^*$</span>The corresponding problem for <span class="math-container">$r=2$</span> (i.e., <a href="https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel%27s_theorem" rel="nofollow noreferrer">Mantel's theorem</a>) is easy since we can enumerate over all triples of vertices in <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2021-09-07T12:18:43.153Z
The problem is not in NP, as it is not even a decision problem. It is in TFNP.
Emil Jeřábek
CC BY-SA 4.0
2021-09-07T12:20:50.600Z
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.
Reijo Jaakkola
CC BY-SA 4.0
2021-09-07T14:34:20.257Z
My bad, have amended the question.
ckamath
<graph-theory><extremal-combinatorics>
Computational complexity of Turán-type problems
ckamath
# Computational complexity of Turán-type problems

(Asked by: username_0 on 2021-09-07)

According to [Turán's theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_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}$](https://en.wikipedia.org/wiki/FNP_(complexity)), and in fact in [$\mathbf{TFNP}$](https://en.wikipedia.org/wiki/TFNP). Moreover, by looking at the original proof of existence (first proof given [here](https://link.springer.com/chapter/10.1007%2F978-3-662-57265-8_41)), it seems to be solvable by polynomial-time algorithm which recursively computes the clique (i.e. the problem is in [$\mathbf{FP}$](https://en.wikipedia.org/wiki/FP_(complexity))). Am I missing something here?

$^\*$The corresponding problem for $r=2$ (i.e., [Mantel's theorem](https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel%27s_theorem)) is easy since we can enumerate over all triples of vertices in $G$.

**Tags:** graph-theory, extremal-combinatorics

> **Comments:**
> **username_1**: The problem is not in NP, as it is not even a decision problem. It is in TFNP.  
> **username_2**: 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.  
> **username_0**: My bad, have amended the question.  

---

## 1 answers

### Answer by username_1 on 2021-09-07. Score: 9 | Accepted answer

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.


---

