When you write "clique algorithm" in Google www.dharwadker.org/clique/ appears as a 2nd result. Citation from abstract:
We present a new polynomial-time algorithm for finding maximal cliques in graphs. (…) The algorithm finds a maximum clique in all known examples of graphs. In view of the importance of the P versus NP question, we ask if there exists a graph for which the algorithm cannot find a maximum clique.
In 4.4 it's written:
Given a simple graph G with n vertices, the algorithm takes less than
$n^8+2n^7+n^6+n^5+n^4+n^3+n^2$ steps to terminate.
So, Dharwadker found an algorithm which is solving NP problem in P time… This would mean that P = NP…
Well, I'm not sure… My guess is that that Dharwadker's algorithm is not correct, i.e. for some input graph, algorithm will not work. That's why he is presenting only "all known examples of graphs", for which obviously his algorithm is working…
Is Dharwadker correct and we have a proof that P = NP? Or you can you present a counter example for his algorithm?
Best Answer
This algorithm is not correct.
(Updated)
http://pastebin.com/KTqSgryK
Paste that file as grapt.txt for Dharwadker app - it won't find that first 5 vertices comprise a clique. This is an example of so-called greedy algorithm, that can quickly find pretty good solution for many start conditions, but its greed can drive it to a trap.