17
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Joshua Grochow
    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$
    – Austin Buchanan
    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$
    – Joshua Grochow
    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$
    – Joshua Grochow
    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
    Dec 1, 2020 at 9:14

0

Reset to default

Your Answer

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