# clique problem in graphs with bounded degree

Is the problem of finding a clique of size $$d$$ in a graph of maximum degree $$d$$ NP-complete ($$d$$ part of the input)?

No (unless $$\text{P}=\text{NP}$$), it can be solved in polynomial time. For each vertex, if it is of degree $$d-2$$ or less it can't be in a clique, and we can skip it. If it is of degree $$d-1$$ there is a single potential clique it could be in (it and all of its neighbors), and we can check it in polynomial time. If it has degree $$d$$ then each of the $$\binom{d}{d-1} = d$$ choices of $$d-1$$ neighbors of it makes a potential clique, and we can check each in polynomial time. This gives an algorithm with time $$O(n d^3)$$, although it's likely possible to do it in time $$O(n d^2)$$ since there's a large amount of overlap between the cliques in case of a vertex of degree $$d$$.

• I think the $O(nd^3)$ -> $O(nd^2)$ speedup is probably easy to achieve by labeling all vertices with numbers $1,2,3,\dots,n$, and when considering a vertex $i$, only consider its neighbours with label $>i$. For every vertex that has $d$ neighbours with larger index, there's $d-1$ vertices that can have at most $d-1$ neighbours with larger index, so this should amortize to $O(nd^2)$. Commented Jul 23, 2023 at 10:51