2
$\begingroup$

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

$\endgroup$

1 Answer 1

7
$\begingroup$

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$.

$\endgroup$
1
  • 2
    $\begingroup$ 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)$. $\endgroup$ Commented Jul 23, 2023 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.