Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$.
-
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$ Jul 23 at 10:51