<p>In terms of using parameters that are possibly much smaller than degeneracy and never larger, there are two results that improve over degeneracy. </p>

<p>First, since the algorithm for degeneracy employs a reduction of the original instance with <span class="math-container">$n$</span> vertices to <span class="math-container">$n$</span> instances with at most <span class="math-container">$d+1$</span> vertices, one may get an algorithm with running time <span class="math-container">$O(1.28^{d-k})$</span> where <span class="math-container">$k$</span> is the clique size as follows: Reduce each of the <span class="math-container">$n$</span> many <span class="math-container">$k$</span>-Clique instances to a <span class="math-container">$d'-k$</span>-Vertex Cover instance with <span class="math-container">$d'\le d+1$</span> and then use the fastest parameterized algorithm for the Vertex Cover problem [1].</p>

<p>Second, there is an algorithm that enumerates all maximal cliques in <span class="math-container">$3^{\gamma /3} n^{O(1)}$</span> time [2]. Herein, the parameter <span class="math-container">$\gamma$</span> is called the <em>weak closure</em> of the input graph. It is the smallest number for which the following holds: </p>

<p>There is an ordering <span class="math-container">$(v_1, v_2, \ldots, v_n)$</span> of the vertices  of the input graph in which every vertex <span class="math-container">$v_i$</span> has in <span class="math-container">$G[v_i,v_{i+1},\ldots,v_n]$</span> at most <span class="math-container">$\gamma-1$</span> common neighbors with every vertex <span class="math-container">$v_j$</span> that is not a neighbor of <span class="math-container">$v_i$</span>. </p>

<p>This parameter is motivated by the observation that in social networks, vertices with many common neighbors tend to be adjacent. It can be easily seen that <span class="math-container">$\gamma\le d$</span> in every graph. Conversely, in a clique on <span class="math-container">$n$</span> vertices we have <span class="math-container">$\gamma=0$</span> and <span class="math-container">$d=n-1$</span>. </p>

<p>[1] <em>Chen, Jianer; Kanj, Iyad A.; Xia, Ge</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2010.06.026" rel="noreferrer"><strong>Improved upper bounds for vertex cover</strong></a>, Theor. Comput. Sci. 411, No. 40-42, 3736-3756 (2010). <a href="https://zbmath.org/?q=an:1205.05217" rel="noreferrer">ZBL1205.05217</a>.</p>

<p>[2] <em>Fox, Jacob; Roughgarden, Tim; Seshadhri, C.; Wei, Fan; Wein, Nicole</em>, <a href="http://dx.doi.org/10.1137/18M1210459" rel="noreferrer"><strong>Finding cliques in social networks: a new distribution-free model</strong></a>,  <a href="https://zbmath.org/?q=an:07206136" rel="noreferrer">ZBL07206136</a>.</p>

CC BY-SA 4.0
2020-06-10T20:52:05.813Z
The first approach is essentially what we did in [this paper](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C37&q=Why+is+maximum+clique+often+easy+in+practice&btnG=). When $d-k$ is a constant it runs in time $O(dm)=O(m^{1.5})$.
Austin Buchanan
CC BY-SA 4.0
2020-06-10T21:24:50.470Z
An FPT algorithm following the first approach was also observed [here](https://fpt.akt.tu-berlin.de/publications/diss-komusiewicz.pdf) for a slight generalization of clique.
Christian Komusiewicz
CC BY-SA 4.0
2020-06-05T20:33:50.560Z
2020-06-05T20:33:50.560Z
Christian Komusiewicz
<p>I don't know if you have checked the tractability of the problem when parameterized by the degeneracy of the input graph (since degeneracy <span class="math-container">$\leq \Delta$</span> ). However, there is an algorithm for the maximum clique on graphs with degeneracy <span class="math-container">$d$</span>, which runs in <span class="math-container">$O^{*}(2^{d/4})$</span>, using the result of Robson (see <a href="https://doi.org/10.1007/s11590-013-0698-2" rel="nofollow noreferrer">here</a>).</p>

CC BY-SA 4.0
2020-06-05T14:05:45.627Z
2020-06-05T15:36:41.303Z
2020-06-05T15:36:41.303Z
Amir Nikabadi
<p>Maximum clique in graphs with degree <span class="math-container">$d$</span> can be reduced to <span class="math-container">$n$</span> instances of maximum clique in a graph with at most <span class="math-container">$d$</span> vertices: for each vertex, compute maximum clique in the induced subgraph of the neighborhood of the vertex.</p>

<p>Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most <span class="math-container">$d$</span> is the same as time complexity of maximum clique in graphs with <span class="math-container">$d$</span> vertices. I think currently the best known (and peer reviewed) algorithm works in <span class="math-container">$O(1.1996^n)$</span> time [1]. Confusingly, there also seems to be an older claimed result with <span class="math-container">$O(1.1892^n)$</span> time [2].</p>

<p>[1] M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set.
Information and Computation, 255:126–146, 2017.</p>

<p>[2] J.M Robson. Finding a maximum independent set in time <span class="math-container">$O(2^{n/4})$</span>. LaBRI, Université de Bordeaux I, Technical report, 2001.</p>

CC BY-SA 4.0
2020-01-27T08:52:36.003Z
Last year, I asked Mike Robson why he did not publish this amazing result, expecting an answer along the line "no one managed to review the paper". The answer turned out to be completely different, essentially, he thought he could do even better and didn't want to rush the result (!).
Arnaud Casteigts
CC BY-SA 4.0
2020-01-27T08:06:57.400Z
2020-01-27T08:06:57.400Z
Laakeri
<p>I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "parameterized algorithm maximum clique" all failed.</p>

<p>What is the best known algorithm for maximum clique problem parameterized by the maximum degree. Or at least, how would you look for something like that?</p>

<ds.algorithms><reference-request><np-hardness><fixed-parameter-tractable>
Best parameterized algorithm for maximum clique
user2316602
# Best parameterized algorithm for maximum clique

(Asked by: username_0 on 2020-01-27)

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "parameterized algorithm maximum clique" all failed.

What is the best known algorithm for maximum clique problem parameterized by the maximum degree. Or at least, how would you look for something like that?

**Tags:** ds.algorithms, reference-request, np-hardness, fixed-parameter-tractable

---

## 3 answers

### Answer by username_4 on 2020-01-27. Score: 13 | Accepted answer

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the neighborhood of the vertex.

Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most $d$ is the same as time complexity of maximum clique in graphs with $d$ vertices. I think currently the best known (and peer reviewed) algorithm works in $O(1.1996^n)$ time [1]. Confusingly, there also seems to be an older claimed result with $O(1.1892^n)$ time [2].

[1] M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set.
Information and Computation, 255:126–146, 2017.

[2] J.M Robson. Finding a maximum independent set in time $O(2^{n/4})$. LaBRI, Université de Bordeaux I, Technical report, 2001.

> **Comments:**
> **username_5**: Last year, I asked Mike Robson why he did not publish this amazing result, expecting an answer along the line "no one managed to review the paper". The answer turned out to be completely different, essentially, he thought he could do even better and didn't want to rush the result (!).  

---

### Answer by username_1 on 2020-06-05. Score: 5

In terms of using parameters that are possibly much smaller than degeneracy and never larger, there are two results that improve over degeneracy.

First, since the algorithm for degeneracy employs a reduction of the original instance with $n$ vertices to $n$ instances with at most $d+1$ vertices, one may get an algorithm with running time $O(1.28^{d-k})$ where $k$ is the clique size as follows: Reduce each of the $n$ many $k$-Clique instances to a $d'-k$-Vertex Cover instance with $d'\le d+1$ and then use the fastest parameterized algorithm for the Vertex Cover problem [1].

Second, there is an algorithm that enumerates all maximal cliques in $3^{\gamma /3} n^{O(1)}$ time [2]. Herein, the parameter $\gamma$ is called the *weak closure* of the input graph. It is the smallest number for which the following holds:

There is an ordering $(v\_1, v\_2, \ldots, v\_n)$ of the vertices of the input graph in which every vertex $v\_i$ has in $G[v\_i,v\_{i+1},\ldots,v\_n]$ at most $\gamma-1$ common neighbors with every vertex $v\_j$ that is not a neighbor of $v\_i$.

This parameter is motivated by the observation that in social networks, vertices with many common neighbors tend to be adjacent. It can be easily seen that $\gamma\le d$ in every graph. Conversely, in a clique on $n$ vertices we have $\gamma=0$ and $d=n-1$.

[1] *Chen, Jianer; Kanj, Iyad A.; Xia, Ge*, [**Improved upper bounds for vertex cover**](http://dx.doi.org/10.1016/j.tcs.2010.06.026), Theor. Comput. Sci. 411, No. 40-42, 3736-3756 (2010). [ZBL1205.05217](https://zbmath.org/?q=an:1205.05217).

[2] *Fox, Jacob; Roughgarden, Tim; Seshadhri, C.; Wei, Fan; Wein, Nicole*, [**Finding cliques in social networks: a new distribution-free model**](http://dx.doi.org/10.1137/18M1210459), [ZBL07206136](https://zbmath.org/?q=an:07206136).

> **Comments:**
> **username_2**: The first approach is essentially what we did in [this paper](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C37&q=Why+is+maximum+clique+often+easy+in+practice&btnG=). When $d-k$ is a constant it runs in time $O(dm)=O(m^{1.5})$.  
> **username_1**: An FPT algorithm following the first approach was also observed [here](https://fpt.akt.tu-berlin.de/publications/diss-komusiewicz.pdf) for a slight generalization of clique.  

---

### Answer by username_3 on 2020-06-05. Score: 5

I don't know if you have checked the tractability of the problem when parameterized by the degeneracy of the input graph (since degeneracy $\leq \Delta$ ). However, there is an algorithm for the maximum clique on graphs with degeneracy $d$, which runs in $O^{\*}(2^{d/4})$, using the result of Robson (see [here](https://doi.org/10.1007/s11590-013-0698-2)).


---

