<p>No (unless <span class="math-container">$\text{P}=\text{NP}$</span>), it can be solved in polynomial time. For each vertex, if it is of degree <span class="math-container">$d-2$</span> or less it can't be in a clique, and we can skip it. If it is of degree <span class="math-container">$d-1$</span> 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 <span class="math-container">$d$</span> then each of the <span class="math-container">$\binom{d}{d-1} = d$</span> choices of <span class="math-container">$d-1$</span> neighbors of it makes a potential clique, and we can check each in polynomial time. This gives an algorithm with time <span class="math-container">$O(n d^3)$</span>, although it's likely possible to do it in time <span class="math-container">$O(n d^2)$</span> since there's a large amount of overlap between the cliques in case of a vertex of degree <span class="math-container">$d$</span>.</p>

CC BY-SA 4.0
2023-07-23T10:51:52.990Z
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)$.
Timon Knigge
CC BY-SA 4.0
2023-07-19T12:51:56.510Z
2023-07-19T12:51:56.510Z
Command Master
<p>Is the problem of finding a clique of size <span class="math-container">$d$</span> in a graph of maximum degree <span class="math-container">$d$</span> NP-complete (<span class="math-container">$d$</span> part of the input)?</p>

<np-hardness><clique>
clique problem in graphs with bounded degree
Michael Poss
# clique problem in graphs with bounded degree

(Asked by: username_0 on 2023-07-19)

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

**Tags:** np-hardness, clique


---

## 1 answers

### Answer by username_1 on 2023-07-19. Score: 7 | Accepted answer

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

> **Comments:**
> **username_2**: 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)$.  

---

