Is this problem in P or NP-Complete?

Question

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?

Answer 1

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.