11
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ cs.stackexchange.com/questions/1176/… may be relevant. $\endgroup$
    – Louis
    Feb 7, 2013 at 12:30
  • $\begingroup$ What are the NO instances? $\endgroup$
    – Yuval Filmus
    Feb 7, 2013 at 14:48
  • 1
    $\begingroup$ @YuvalFilmus He's asking the problem is $\alpha(G) = |G| / 2$ where $|G|$ is the order of the graph. It should be possible to pad some isolated vertices onto the graph to boost the independence number. Mohammad, do you know the reduction? Is it not possible to add $n/2 - k$ isolated vertices to get the wanted reduction? $\endgroup$
    – Pål GD
    Feb 7, 2013 at 16:32
  • $\begingroup$ No, I don't have a reduction. $\endgroup$
    – Mohammad Al-Turkistany
    Feb 7, 2013 at 17:39
  • 2
    $\begingroup$ @PålGD The reduction wouldn't work, since the usual problem asks whether $\alpha(G) \geq k$ rather than $\alpha(G) = k$. In fact, it's not even clear that the problem is in NP. $\endgroup$
    – Yuval Filmus
    Feb 7, 2013 at 20:58

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ YuvalFilmus Thanks a lot. Does this give polynomial time algorithm for my problem? $\endgroup$
    – Mohammad Al-Turkistany
    Feb 8, 2013 at 12:14
  • $\begingroup$ I think so - do you agree? $\endgroup$
    – Yuval Filmus
    Feb 8, 2013 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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