Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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!

share|improve this question

closed as off topic by Jukka Suomela, JɛffE, Tsuyoshi Ito, Suresh Venkat Mar 13 '12 at 5:33

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
Your questions are unclear: are you interested in listing all elements of that set in polynomial time? Or in computing their cardinality? –  Anthony Labarre Mar 10 '12 at 10:46
3  
Homework problems are off-topic here; you might want to try math.stackexchange.com –  Jukka Suomela Mar 10 '12 at 10:53
    
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. –  Kaveh Mar 10 '12 at 15:42