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) Is the 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 in polynomial time or NP-complete?

2) Is the set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k 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!

  • 1
    $\begingroup$ Your questions are unclear: are you interested in listing all elements of that set in polynomial time? Or in computing their cardinality? $\endgroup$ – Anthony Labarre Mar 10 '12 at 10:46
  • 3
    $\begingroup$ Homework problems are off-topic here; you might want to try math.stackexchange.com $\endgroup$ – Jukka Suomela Mar 10 '12 at 10:53
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Mar 10 '12 at 15:42