<p>Given a connected simple graph <span class="math-container">$G=(V,E)$</span>, let <span class="math-container">$d$</span> denote its <a href="https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)" rel="noreferrer">degeneracy</a> and let <span class="math-container">$\omega$</span> denote the size of a <a href="https://en.wikipedia.org/wiki/Clique_problem" rel="noreferrer">maximum clique</a>.</p>
<p>A well-known bound on the clique number is <span class="math-container">$\omega\le d+1$</span>, which is helpful when solving the maximum clique problem or when <a href="https://dl.acm.org/doi/abs/10.1145/2543629?casa_token=fxzBWpiA1ZsAAAAA:CrMNWZ-0GU9DU3L0-UE43AniI2H-2gvXWFzx341kOOA8MvUU2QnCVAQUxcpoQQGtfriWot8YZGi9TA" rel="noreferrer">enumerating all maximal cliques</a>.</p>
<p>How fast can one test whether this bound is tight, <span class="math-container">$\omega=d+1$</span>? An algorithm that runs in time <span class="math-container">$O(dm)=O(m^{1.5})$</span> is <a href="https://pubsonline.informs.org/doi/10.1287/opre.2019.1970" rel="noreferrer">known</a>.</p>
<p>Is there a faster algorithm, say, running in linear time?</p>
<p>Or, is <span class="math-container">$O(m^{1.5})$</span> best possible under something like <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="noreferrer">SETH</a>?</p>

CC BY-SA 4.0
2020-12-01T03:30:54.623Z
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?
Joshua Grochow
CC BY-SA 4.0
2020-12-01T04:06:00.643Z
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).
Austin Buchanan
CC BY-SA 4.0
2020-12-01T06:05:37.347Z
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...
Joshua Grochow
CC BY-SA 4.0
2020-12-01T06:08:22.627Z
Um...it looks like their article was *just* published and they list your question as Open Problem 1 (minus the possible connection to SETH)...
Joshua Grochow
CC BY-SA 4.0
2020-12-01T09:14:47.353Z
Maybe you are aware, but this problem recently appeared in codeforces https://codeforces.com/contest/1439/problem/B. It seems nobody in the discussion mentions anything better than $O(m^{1.5})$.
Laakeri
<graph-algorithms><parameterized-complexity><clique><fixed-parameter-tractable>
Linear-time algorithm to test if clique number equals degeneracy bound?
Austin Buchanan
# Linear-time algorithm to test if clique number equals degeneracy bound?

(Asked by: username_0 on 2020-11-30)

Given a connected simple graph $G=(V,E)$, let $d$ denote its [degeneracy](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) and let $\omega$ denote the size of a [maximum clique](https://en.wikipedia.org/wiki/Clique_problem).

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](https://dl.acm.org/doi/abs/10.1145/2543629?casa_token=fxzBWpiA1ZsAAAAA:CrMNWZ-0GU9DU3L0-UE43AniI2H-2gvXWFzx341kOOA8MvUU2QnCVAQUxcpoQQGtfriWot8YZGi9TA).

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](https://pubsonline.informs.org/doi/10.1287/opre.2019.1970).

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

Or, is $O(m^{1.5})$ best possible under something like [SETH](https://en.wikipedia.org/wiki/Exponential_time_hypothesis)?

**Tags:** graph-algorithms, parameterized-complexity, clique, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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).  
> **username_1**: 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...  
> **username_1**: Um...it looks like their article was *just* published and they list your question as Open Problem 1 (minus the possible connection to SETH)...  
> **username_2**: Maybe you are aware, but this problem recently appeared in codeforces https://codeforces.com/contest/1439/problem/B. It seems nobody in the discussion mentions anything better than $O(m^{1.5})$.  

---

## 0 answers

