I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems.

1) L = set of all (G, k) where G is a graph with maximum degree of at most 4 and contains an independent set of size at least k. Is L in polynomial time or NP-complete?

2) L = set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k. Is L in P or NP-complete?

Since both Independent Set and Clique are NP-Complete, my first instinct is to say that 1) and 2) are both NP-complete. However, due to the bounded degree restriction, that is likely not true. I am not quite sure what I should be reducing from. Since if I were to attempt to show they are in P, I would have to reduce from something in P and I don't know anything that are remotely similar except Clique and Ind. Set, but like I said, those are NP-complete. I would really appreciate any help I can get with those two proofs. Any proof or hint would be very welcome!

EDIT: Actually after some research it seems that Independent Set problems tend to be NP-Complete when it comes to bounded degree graphs while Clique can usually be found in P-time or even linear time. I am not sure about this case, but it's a start I suppose.

  • $\begingroup$ Hmm...this is very odd. I just so happened to come across the exact same problems on a final I took three days ago. Coincidence?! I THINK NOT. $\endgroup$ – user26840 Mar 13 '12 at 16:27

Hint for (1): Look at the proof that independent set is NP-complete. [Not sure about that one, but worth a try]

Hint for (2): Suppose that $G$ was a graph with maximum degree $1$. Generalize.

  • $\begingroup$ Well if the max degree is 1, then the clique can have at most size 2. That can be verified in P time by just crawling through the vertices, I am not sure about how to generalize that into a reduction. $\endgroup$ – Eric Mercer Mar 10 '12 at 22:30
  • $\begingroup$ @Eric: In order to prove that the problem is in P, you don't need to present a reduction. Just a polynomial-time algorithm for solving it directly will do. $\endgroup$ – Henning Makholm Mar 12 '12 at 3:00
  • $\begingroup$ Right, I am just not sure how to generalize from a graph of max degree 1. $\endgroup$ – Eric Mercer Mar 12 '12 at 3:18

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.