0
$\begingroup$

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.

  • 0
    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.2012-03-13

1 Answers 1

3

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.

  • 0
    Right, I am just not sure how to generalize from a graph of max degree 1.2012-03-12