1
$\begingroup$

I need to determine if the following problem is in P or NP-Complete:

$\mathrm{2-IS} = \{\left< G, k\right > | G \text{ is a graph which every node in it has a degree 2 AND there is an independent set of size $k$ in $G$}\}$

My intuition says it's in NP-Complete but I can't find another NP-Complete problem to reduce it to... any help?

$\endgroup$
  • $\begingroup$ Hint: Think about how graphs where every node has degree 2 look like. $\endgroup$ – sdcvvc May 28 '13 at 18:32
  • 2
    $\begingroup$ If every node has degree 2, then it must be the union of cycles of length $k_i$. There is an independent set of size $\sum\lfloor \frac{k_i + 1}{2} \rfloor$. $\endgroup$ – Calvin Lin May 28 '13 at 18:32
  • $\begingroup$ @Calvin: Of course $\left\lfloor\frac{k_i+1}2\right\rfloor=\left\lceil\frac{k_i}2\right\rceil$. $\endgroup$ – Rahul May 28 '13 at 18:36
  • $\begingroup$ @CalvinLin what is ki? please further explain $\endgroup$ – DanielY May 28 '13 at 18:40
  • 2
    $\begingroup$ The main idea is that the graphs in which every vertex has degree 2 are very simple. So simple that one can actually find the size of their maximum independent set in polynomial time. Calvin hinted that such graphs are just composed of one or more disjoint cycles -- so it might be a good idea to look at what can we say about independent sets in a cycle (clearly, if the graph consists of more than one cycle, they can be treated... independently) $\endgroup$ – Peter Košinár May 28 '13 at 19:12
3
$\begingroup$

Here are a few ingredients you might find useful for cooking the polynomial algorithm for 2-IS (no, it's not NP-complete; unless P=NP):

  • Checking if every node in a graph has degree $2$ is easy.
  • A graph in which every node has degree $2$ is a disjoint union of one or more cycles.
  • The size of maximum independent set of a cycle on $n$ nodes is $\lfloor\frac{n}{2}\rfloor$.
  • Finding all the cycles can be performed by a depth-first search, for example.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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