Is The Clique Algorithm by Ashay Dharwadker correct?

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.


I doubt if it is correct. His profile tells us that apart from finding a polynomial time algorithm for maximal cliques in Graphs, he has also connected four color theorem to Standard Model in physics and has predicted Higgs-Boson from four color theorem apart from calculating Einstein's cosmological constant in his spare time:

http://www.dharwadker.org/profile.html

He claims to be the founder and director of Institute of Mathematics, Gurgaon (India). Being an Indian, I can tell that I have never heard of this institute. Most likely he is an amateur mathematician.


From the paper's introduction (haven't and probably won't read the whole thing):

We prove that every graph with n vertices and minimum vertex degree $\delta$ must have a maximum clique of size at least $\lceil \frac n{n−\delta}\rceil$ and that the algorithm will always find a clique of at least this size.

This seems to be a reasonable claim. It does not actually solve the clique problem, since it only finds "large" cliques in a specific sense. However, he seems to be more interested in the Ramsey theory connection:

Furthermore, we prove that this condition is the best possible in terms of $n$ and $\delta$ by explicitly constructing graphs for which the size of a maximum clique is exactly $\lceil \frac n{n−\delta}\rceil$

I thought he might be misinterpreting the actual question, since finding a lower bound on maximal cliques and then demonstrating it is an upper bound on some graphs is not sufficient to solve the clique problem. But then he writes:

In Section 7, we demonstrate the algorithm by finding maximum cliques for several EXAMPLES of famous graphs, including two large benchmark graphs with hidden maximum cliques.

which seems to indicate that he does admit his algorithm does not find maximal cliques in all circumstances.

My judgement: I wouldn't dismiss it out of hand, the author is not obviously a crank, the algorithm might be correct and even interesting, but it does not solve P=NP.