Comments on What's the complexity of this algorithm for solving the maximum clique NP-Complete problem?
Parent
What's the complexity of this algorithm for solving the maximum clique NP-Complete problem?
I believe I have discovered a quasi-polynomial algorithm for solving an NP-Complete problem: the maximum clique problem.
Of course, I doubt the correctness of my discovery, because as we know, that's known to be quite difficult and unlikely.
I'll present here the essential algorithm (without optimizations that are unnecessary for reaching QP complexity). I'm interested in finding whether my evaluation of the worst-case complexity is correct.
The algorithm below is recursive:
-
Take as input the minimum size that a solution must have to be a better clique than those known so far (initially, use 1). Let's call it Z.
-
Take as input a problem that has nodes, some of which are connected through edges. Let's call this problem P.
-
Create an empty solution list. Let's call it S.
-
2bis) [Edit: I forgot to include this step]
Remove any nodes that have less than Z-1 edges. Repeat this operation as necessary.
- Create a copy of P. Let's call it A. It holds the only candidates that can be selected in step 4. At the moment, all nodes of P are also contained in A.
loop:
-
Find the best candidate node. Let's call it X.
The candidate node must exist in A. From those that exist in A, select the one with less edges in P, even if this might seem counter-intuitive.
-
If there are no candidates, print S (it might be empty), and terminate (if we were recursing, continue at step 9 of the previous level of recursion; otherwise, we've finished).
-
Create a temporary solution list containing exactly X. Let's call it ST.
-
Create a smaller problem Q, which is a copy of P, but removing any nodes not connected with X, and also removing X.
-
Solve (recursively, goto step 0) the problem Q. Pass MAX(Z-1, 1) as the input for step 0, and Q as the input for step 1.
Because X is the least-connected node, Q is the smallest problem we could try to solve. Considering that p (which is 0<=p<=1) is the frequency of edges in the problem P, and n is the number of nodes in the problem P, Q will have no more than
n*pnodes. -
Append the output of the previous step to the list ST.
-
If the size of the list ST is greater or equal than Z, replace S with the contents of ST, and update Z to be the size of ST plus 1.
-
Remove ST.
-
Create a copy of P. Let's call it AT.
-
Remove from AT all nodes that are connected to X, and remove also X from A.
The reason is that we've found the best solution that contains X, and thus if we want a better solution, it cannot contain X, and it must contain at least one node not compatible with X. Actually, because we want a better solution, we need at least two nodes not connected to X. Thus,
-
For each node that exists in A and/or in AT, if in any of those graphs the node is not connected to any other nodes, remove such node from all of P, A, and AT. (Edited, as I had forgotten a detail.)
These can only start a solution as good as S, but not better.
-
Remove X from P.
-
15bis) [Edit: I forgot to include this step]
Remove any nodes that have less than Z-1 edges in P from both P, A, and AT.
-
If AT contains less nodes than A, replace A with the contents of AT.
This is an optimization, so that we use the smallest A (alternatives list), which reduces the number of iterations in the loop. This reduces the base of the exponential function, but is not necessary for the algorithm being QP.
-
Remove AT.
-
goto step 4 (loop);
Signed-off-by: Alejandro Colomar Andrés <[email protected]>
(Note: This was all human generated; I haven't used any LLM or AI at all for developing this algorithm; just my brain.)
This is the first time I publish this algorithm. I will soon publish my own implementation, which contains a few important optimizations. (If you try implementing the above, you'll find it's very very slow, and some optimizations not mentioned here are necessary to make it be actually fast.)
In steps 4 and 8 are the key to the super-polynomial complexity.
The number of times we repeat step 4 across all recursion levels is essential to the complexity of the algorithm. (Then, that's multiplied by the complexity of each iteration, but that is polynomial, so let's ignore that part.)
Some interesting facts:
- The depth of recursion will not grow past the size of the maximum clique.
- The size of the problems P will diminish until it's 0 at the depth of recursion of the size of the maximum clique.
- When getting close to that recursion level, p will grow to 1.
The amount of iterations of step 4 in a given recursion level is bound by the number of nodes at that level.
The first levels of recursion will reduce the size faster than n*p^d where d is the depth level, given we choose candidates with number of edges below average. We might worry about the deeply recursive levels, where we got rid of the nodes with few edges, and only highly connected nodes remain.
Let's start by assuming that p is homogeneous across all nodes, so that all nodes have n*p edges, all the time. It's obvious that the size of the problem at each level of recursion will be p times the size of the previous level of recursion. That way, we'll reach size 1 (and thus terminate recursing) when n*p^d == 1, where d is the depth of recursion. We can calculate d = log(n)/log(1/p).
Now, if we drop the assumption that p is homogeneous, we have to calculate the size as n*p1*p2*p3*p4..., where p1,p2,p3... are the pi values of the best candidate X at each level of recursion. Because on average they must be more or less equal to p, some will be smaller, and others will be higher. We also start by the lowest values, and only reach the high values as needed, so on average we remain below p.
Now, similar to how the geometric mean is never larger than the arithmetic mean, it seems obvious that the multiplication of non-homogeneous values will always result in a value smaller than the multiplication of homogeneous values.
By the end of the run of this algorithm, we'll be trying the remaining (highly connected) nodes at low recursion depths, which might also seem problematic. However, at that point, the number of edges of each node has dropped below half of the original, and thus, p must again be below average for those nodes.
As an exception to the above paragraph, in problems with disjoint subgraphs, with low p, the initial removal of nodes might not affect the p of the remaining last nodes. However, each of those disjoint subgraphs can be considered a smaller problem with a higher p, and the same applies to each smaller problem. Near the end, we'll face a problem of small n and high p, and the rules above will apply.
Thus, I believe I've proved that regardless of the distribution of p, the complexity of the exponent is bound by log(n)/log(1/p).
If the exponent is bound by a logarithm, and of course, the number of iterations of the loop in a given recursive call is bound by n, we can find the upper bound for the number of total iterations of step 4 by n^(log(n)/log(1/p)).
I've actually implemented this algorithm in a combination of shell scripts and C programs, and the number of iterations of each level of recursion, and the maximum depth reached, both seem to agree with these theoretical bounds. Actually, while they never surpass those bounds, they seem to be even better than those theoretical bounds. Also, I've run the implementation with several of the benchmarks I found at https://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark#detC125.9, and it agrees with the size of the maximum cliques, which makes me confident of the correctness of the algorithm (unrelated to its complexity).
Is all of this correct, or did I make any mistakes in my evaluation of the complexity?
Here are a few runs that seem to agree with the theory here:
N = 100, p = 0.9
$ time npc-rand 100 0.9 0 | npc-solve 100 | wc -l
Size: 100
Frequency: 0.900000
Seed: 0
13 0
151 1
1369 2
8148 3
18268 4
8259 5
464 6
11 7
9 8
9 9
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
8 21
7 22
6 23
5 24
4 25
3 26
2 27
2 28
1 29
30
real 8m42.176s
user 6m55.197s
sys 1m52.039s
N = 60, p = 0.9
$ time npc-rand 60 0.9 0 | npc-solve 60 | wc -l
Size: 60
Frequency: 0.900000
Seed: 0
9 0
39 1
48 2
11 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
1 22
1 23
24
real 0m1.142s
user 0m1.483s
sys 0m0.288s
Post
(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, p. 129. Even the heuristic of choosing the minimum-degree vertex is the same!
ArXiv preprint 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:
- subexponential when p is constant, or p = φ(n)/n for some function φ such that φ(n) = o(n), with φ → ∞ when n → ∞;
- exponential for p = k/n, if k is a fixed constant.
I have not yet deciphered their proof of this assertion.
4 comment threads