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

$\endgroup$
  • 5
    $\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

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.