Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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).
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.
