Post History
#4: Post edited
by
clemens
·
2026-05-15T01:40:01Z (4 months ago)
- (Status of this answer: mostly complete, but I lack sufficient knowledge in the area)
- The algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
[ArXiv preprint 1505.04969](https://arxiv.org/pdf/1505.04969) appears to show that this branch-and-bound algorithm exhibits exponential complexity for random graphs. It also links to another paper, "Analysis of an exhaustive search algorithm in random graphs and the n^{c log n}-asymptotics", which seems pertinent.- "Theorem 1" of the first paper says:
- > The average running time of exhaustive search for max independent set
- when running in (n, p)-binomial random graph G of order n is:
- > 1. subexponential when p is constant, or p = φ(n)/n for some function φ such that φ(n) = o(n), with φ → ∞ when n → ∞;
- > 2. exponential for p = k/n, if k is a fixed constant.
- I have not yet deciphered their proof of this assertion.
- (Status of this answer: mostly complete, but I lack sufficient knowledge in the area)
- The algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
- [ArXiv preprint 1505.04969](https://arxiv.org/pdf/1505.04969) appears to show that this branch-and-bound algorithm exhibits exponential complexity for random graphs. It also links to another paper, "Analysis of an exhaustive search algorithm in random graphs and the $n^{c log n}$-asymptotics", which seems pertinent.
- "Theorem 1" of the first paper says:
- > The average running time of exhaustive search for max independent set
- when running in (n, p)-binomial random graph G of order n is:
- > 1. subexponential when p is constant, or p = φ(n)/n for some function φ such that φ(n) = o(n), with φ → ∞ when n → ∞;
- > 2. exponential for p = k/n, if k is a fixed constant.
- I have not yet deciphered their proof of this assertion.
#3: Post edited
by
clemens
·
2026-05-15T01:39:50Z (4 months ago)
added solution
Not a complete answer but the algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!This branch-and-bound algorithm is presumably exponential (and indeed, given the 3-SAT→MaxClique translation, presumably has a growth rate higher than $O(1.02^n)$). I have not yet seen concrete worst-cases that would illustrate this exponential growth, though.
- (Status of this answer: mostly complete, but I lack sufficient knowledge in the area)
- The algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
- [ArXiv preprint 1505.04969](https://arxiv.org/pdf/1505.04969) appears to show that this branch-and-bound algorithm exhibits exponential complexity for random graphs. It also links to another paper, "Analysis of an exhaustive search algorithm in random graphs and the n^{c log n}-asymptotics", which seems pertinent.
- "Theorem 1" of the first paper says:
- > The average running time of exhaustive search for max independent set
- when running in (n, p)-binomial random graph G of order n is:
- > 1. subexponential when p is constant, or p = φ(n)/n for some function φ such that φ(n) = o(n), with φ → ∞ when n → ∞;
- > 2. exponential for p = k/n, if k is a fixed constant.
- I have not yet deciphered their proof of this assertion.
#2: Post edited
by
clemens
·
2026-05-07T23:24:37Z (4 months ago)
- Not a complete answer but the algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
This branch-and-bound algorithm, as it is relatively well-known, must be exponential, hence not quasipolynomial; but I have not seen the reasoning behind why it is exponential.
- Not a complete answer but the algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
- This branch-and-bound algorithm is presumably exponential (and indeed, given the 3-SAT→MaxClique translation, presumably has a growth rate higher than $O(1.02^n)$). I have not yet seen concrete worst-cases that would illustrate this exponential growth, though.
#1: Initial revision
by
clemens
·
2026-05-07T23:18:22Z (4 months ago)
Not a complete answer but the algorithm as described in the OP and with the clarifications in the comments appears equivalent to the branch-and-bound algorithm described in [Li & Quan 2010](https://ojs.aaai.org/index.php/AAAI/article/view/7536/7397), p. 129. Even the heuristic of choosing the minimum-degree vertex is the same! This branch-and-bound algorithm, as it is relatively well-known, must be exponential, hence not quasipolynomial; but I have not seen the reasoning behind why it is exponential.