Given a connected simple graph $G=(V,E)$, let $d$ denote its degeneracy and let $\omega$ denote the size of a maximum clique.

A well-known bound on the clique number is $\omega\le d+1$, which is helpful when solving the maximum clique problem or when enumerating all maximal cliques.

How fast can one test whether this bound is tight, $\omega=d+1$? An algorithm that runs in time $O(dm)=O(m^{1.5})$ is known.

Is there a faster algorithm, say, running in linear time?

Or, is $O(m^{1.5})$ best possible under something like SETH?

  • 2
    $\begingroup$ Can't you just compute the k-core decomposition (which is quasilinear time IIRC), and then just check if the last core is a clique? $\endgroup$ Commented Dec 1, 2020 at 3:30
  • 3
    $\begingroup$ The decomposition is linear time, but I don’t think that solves the problem. It works, for example, for G=C_3 or G=C_4 but fails for their disjoint union (or for their disjoint union with an added edge between them). $\endgroup$ Commented Dec 1, 2020 at 4:06
  • 3
    $\begingroup$ Ah, I see now. (After your comment, I thought I could answer your Q, but then looked at the article and saw I just rediscovered their algorithm in the case $p=0$.) I wonder if you don't even need SETH - it seems like maybe it's possible to show that if you could do better than $O((m+n) + d^2 n)$ (which is what they have) then either you'd be able to compute $k$-cores faster than linear (not possible by query complexity) or test whether a $d$-vertex graph is a clique in $o(d^2)$ (also not possible by query complexity). I don't quite see a reduction, but maybe one can do it w/o SETH... $\endgroup$ Commented Dec 1, 2020 at 6:05
  • 4
    $\begingroup$ Um...it looks like their article was just published and they list your question as Open Problem 1 (minus the possible connection to SETH)... $\endgroup$ Commented Dec 1, 2020 at 6:08
  • 5
    $\begingroup$ Maybe you are aware, but this problem recently appeared in codeforces codeforces.com/contest/1439/problem/B. It seems nobody in the discussion mentions anything better than $O(m^{1.5})$. $\endgroup$
    – Laakeri
    Commented Dec 1, 2020 at 9:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.