<p>Take an abitrary instance of the independent set problem: given an $n$-vertex graph $H=(V,E)$ and an integer $k\ge1$, does $H$ contain an independent set on $k$ vertices.</p>

<p>Construct a new graph $G$ that is the disjoint union of graph $H$, a clique $C$ on $n+k$ vertices and an independent set $I$ on $n$ vertices.
Note that $\omega(G)=n+k$.</p>

<ul>
<li>If $H$ contains an independent set on $k$ vertices, then $\alpha(G)\ge n+k+1$.
You may use the $k$-element independent set in $G$, the $n$ vertices in $I$, and one vertex from $C$.</li>
<li>If $H$ does not contain an independent set on $k$ vertices, then $\alpha(G)\le n+k$.</li>
</ul>

<p>Hence by comparing $\omega(G)$ and $\alpha(G)$, you can answer arbitrary instances of the NP-hard independent set problem.</p>

CC BY-SA 3.0
2015-02-15T13:43:22.713Z
2015-02-15T13:43:22.713Z
Gamow
<p>Given an arbitrary graph $G$, could there be a polynomial time algorithm to tell if it has a larger size clique $(\omega(G))$ or larger independence number$(\alpha(G))$? </p>

CC BY-SA 3.0
2015-02-16T13:53:56.307Z
So you are asking whether the decision problem of whether $\omega(G) < \alpha(G)$ is in P?
András Salamon
CC BY-SA 3.0
2015-02-16T20:25:31.637Z
@AndrásSalamon yes apparently it is not.
Turbo
<cc.complexity-theory><ds.algorithms>
Deciding CL-IS on graph efficiently
Turbo
# Deciding CL-IS on graph efficiently

(Asked by: username_0 on 2015-02-15)

Given an arbitrary graph $G$, could there be a polynomial time algorithm to tell if it has a larger size clique $(\omega(G))$ or larger independence number$(\alpha(G))$?

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: So you are asking whether the decision problem of whether $\omega(G) < \alpha(G)$ is in P?  
> **username_0**: @AndrásSalamon yes apparently it is not.  

---

## 1 answers

### Answer by username_2 on 2015-02-15. Score: 5 | Accepted answer

Take an abitrary instance of the independent set problem: given an $n$-vertex graph $H=(V,E)$ and an integer $k\ge1$, does $H$ contain an independent set on $k$ vertices.

Construct a new graph $G$ that is the disjoint union of graph $H$, a clique $C$ on $n+k$ vertices and an independent set $I$ on $n$ vertices.
Note that $\omega(G)=n+k$.

* If $H$ contains an independent set on $k$ vertices, then $\alpha(G)\ge n+k+1$.
  You may use the $k$-element independent set in $G$, the $n$ vertices in $I$, and one vertex from $C$.
* If $H$ does not contain an independent set on $k$ vertices, then $\alpha(G)\le n+k$.

Hence by comparing $\omega(G)$ and $\alpha(G)$, you can answer arbitrary instances of the NP-hard independent set problem.


---

