[Solved]: Independent set on cubic triangle-free graphs

Problem Detail: 

I know that maximum independent set on cubic triangle-free graphs is NP-complete.

Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$?

Basiclly, YES instance of independent set problem on cubic triangle-free graphs problem must have exactly $|V|/2$ nodes. NO instance has an independent set of size less than $|V|/2$.

Asked By : Mohammad Al-Turkistany

Answered By : Yuval Filmus

Let's start by proving that the maximum independent set is of size at most $|V|/2$. Let $I$ be an independent set. For each vertex $v$, let $\alpha(v)$ be the number of its neighbors in $I$. If $\alpha(v) \geq 1$, then we know that $v \notin I$. Since the graph is cubic, $\sum_v \alpha(v) = 3|I|$. Since $\alpha(v) \leq 3$, the number of vertices such that $\alpha(v) \geq 1$ is at least $|I|$. Hence $|I| \leq |V|/2$.

When can we have equality? We must have $\alpha(v) \in \{0,3\}$, so for each vertex not in $I$, all its neighbors must be in $I$. The converse is also true - for each vertex in $I$, all its neighbors are not in $I$. In other words, the graph must be bipartite. This can be checked in polynomial time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9572

 Ask a Question

 Download Related Notes/Documents