10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Well, he cannot have tested "all known examples of graphs". $\endgroup$ – Chris Godsil Mar 18 '13 at 15:26
  • $\begingroup$ @ChrisGodsil So, you are sure that he is wrong? $\endgroup$ – Adam Stelmaszczyk Apr 7 '13 at 15:45
  • 3
    $\begingroup$ if someone states they have tested an algorithm on "all known examples" of graphs, then I do not believe them. And I incline to scepticism about any related mathematical claims they make. $\endgroup$ – Chris Godsil Apr 7 '13 at 17:19
  • $\begingroup$ Thank you, I also don't believe him. $\endgroup$ – Adam Stelmaszczyk Apr 7 '13 at 18:11
  • 1
    $\begingroup$ GI is conjectured to be in NPI so GI in P would not affect P vs NP in that scenario. more on this: is anyone aware of a counterexample to the Dharwadker GI algorithm/ Theoretical Computer Science $\endgroup$ – vzn Aug 13 '15 at 2:06
9
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Can you post (eg on pastebin) one of your example graphs where Dharwadker’s algorithm fails, so that others can verify this failure? $\endgroup$ – Peter LeFanu Lumsdaine Oct 22 '13 at 16:10
  • 2
    $\begingroup$ pastebin.com/KTqSgryK $\endgroup$ – KonstKaras Oct 23 '13 at 2:00
  • $\begingroup$ Here is a counterexample for his other P=NP attempt (Hamiltonian cycle one: dharwadker.org/hamilton ): pastebin.com/jqZ6d3dm (use as graph.txt for his app). Hamiltonian cycle exists for this graph (it is $1,2,3,\dots,13,1$) but his algorithm finds only a path with 12 out of 13 vertices. $\endgroup$ – Fiktor Mar 11 '15 at 3:03
  • $\begingroup$ have you actually verified this example with their code? program output would be helpful $\endgroup$ – vzn Aug 13 '15 at 2:08
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.