patternMinor
Independent set on cubic triangle-free graphs
Viewed 0 times
cubicfreeindependentgraphstriangleset
Problem
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$.
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$.
Solution
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.
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.
Context
StackExchange Computer Science Q#9572, answer score: 7
Revisions (0)
No revisions yet.