# NP-Completeness of Certain Bounded Degree Graphs

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.

• 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. – user26840 Mar 13 '12 at 16:27

## 1 Answer

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.

• 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. – Eric Mercer Mar 10 '12 at 22:30
• @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. – Henning Makholm Mar 12 '12 at 3:00
• Right, I am just not sure how to generalize from a graph of max degree 1. – Eric Mercer Mar 12 '12 at 3:18