# Linear-time algorithm to test if clique number equals degeneracy bound?

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?

• 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? Dec 1 '20 at 3:30
• 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). Dec 1 '20 at 4:06
• 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... Dec 1 '20 at 6:05
• Um...it looks like their article was just published and they list your question as Open Problem 1 (minus the possible connection to SETH)... Dec 1 '20 at 6:08
• 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})$. Dec 1 '20 at 9:14