3
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 7
    $\begingroup$ 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 (!). $\endgroup$ – Arnaud Casteigts Jan 27 at 8:52
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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, Theor. Comput. Sci. 411, No. 40-42, 3736-3756 (2010). ZBL1205.05217.

[2] Fox, Jacob; Roughgarden, Tim; Seshadhri, C.; Wei, Fan; Wein, Nicole, Finding cliques in social networks: a new distribution-free model, ZBL07206136.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The first approach is essentially what we did in this paper. When $d-k$ is a constant it runs in time $O(dm)=O(m^{1.5})$. $\endgroup$ – Austin Buchanan Jun 10 at 20:52
  • 1
    $\begingroup$ An FPT algorithm following the first approach was also observed here for a slight generalization of clique. $\endgroup$ – Christian Komusiewicz Jun 10 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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