I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity.

The algorithm is as follows :

  1. Label all the vertices with distinct prime numbers.
  2. Label all edges with weight equal to 1.
  3. Now remove one vertex at a time, while removing a vertex v, if there is edge between u and v & v and w, then add a edge between u and w, with weight = weight(u->v)*weight(v->w)*label(v)
  4. If at the end you end up with only one vertex with self edges and if there is a self edge that is equal to the product of all the primes of the removed vertices then there is Hamiltonian Cycle.

I have proved the algorithm is correct but unable to find it's time complexity. I think there can be much more optimization in this algorithm also, as we don't need to add those edges to the graph that whose weight divides the weight of some other already present edge. If someone can give some optimization to this algorithm it may turn out to be polynomial, thus proving P = NP.

  • 5
    $\begingroup$ It seems that the number of edges (assuming you allow two edges between the same vertices with different weights) will become exponential (as there can be an edge with distinct weight for every subset of vertices). Using prime numbers just obfuscates what the algorithm is doing, namely keeping track of subsets of vertices. There's no good reason this approach has any viability and could lead to a proof of $P=NP$. Even if it did, discussion/development of scientific "breakthroughs" does not belong on a question and answer site but rather on something more like a forum. $\endgroup$ – Tom van der Zanden Nov 28 '15 at 17:28
  • $\begingroup$ Yeah, I too had a feeling of like the number of edges going exponential but if we can intelligently remove the unnecessary edges then the complexity might go down, also for sparse graphs this algorithm will do pretty good. $\endgroup$ – Saurabh Jain Nov 28 '15 at 17:32
  • $\begingroup$ Are you assuming you can multiply large numbers in constant time? $\endgroup$ – Mike Samuel Dec 7 '15 at 22:20
  • $\begingroup$ Actually we don't need to multiply the numbers, we can just keep the set of all prime numbers to be multiplied. $\endgroup$ – Saurabh Jain Dec 11 '15 at 14:43

Unfortunately, whenever you start thinking about algorithms that use the nice prime factorization property things start breaking down. Why? You never said how you could generate $n$ prime numbers. That is not $\in P$, in fact that is still an open problem in mathematics, how many prime numbers are there? So even though the algorithm amy be suitable for small input sizes it is not theoretically sound.

| cite | improve this answer | |
  • 3
    $\begingroup$ This answer is incorrect. Generating prime numbers can be done in polynomial time. See, e.g., en.wikipedia.org/wiki/Primality_test#Fast_deterministic_tests. $\endgroup$ – D.W. Nov 29 '15 at 0:22
  • 2
    $\begingroup$ I know -- and you can use polynomial-time primality testing to generate primes, simply by trial and error (pick a number, test if it is prime, and if not, repeat). In this way you can generate $n$ prime numbers in time polynomial in $n$, so this answer's claim is not correct. $\endgroup$ – D.W. Nov 29 '15 at 0:30
  • 3
    $\begingroup$ As I see it, there are only $n=|V|$ different primes needed. If you think this is not accurate, please edit the question to give a more detailed running time analysis and justification for why it can't be done in polynomial time. $\endgroup$ – D.W. Nov 29 '15 at 1:01
  • 1
    $\begingroup$ @user2879934 If you pick a random integer $x$, then the probability that $x$ is prime is $\Theta(1/\log x)$. In fact, you don't even need to use the (extremely efficient) method of picking random numbers and testing them as D.W. suggested. If you want to generate $n$ prime numbers, then you just need to run the Sieve of Eratosthenes in the first $\Theta(n\log n)$ numbers, which is polynomial. $\endgroup$ – Tom van der Zanden Nov 29 '15 at 9:19
  • 1
    $\begingroup$ @user2879934 I agree no prime generating formula is known, but that's not what we're discussing here. Your answer is incorrect, using the Sieve of Eratosthenes will allow you to generate the primes required for the suggested algorithm in deterministic, polynomial, worst-case time. The sieve is exponential only in the input size, to generate $n$ distinct primes we just need to run the Sieve for integers up to $\Theta(n \log n)$. In that case the input size is $\Theta(\log{(n\log n)})$ and the running time is thus polynomial. $\endgroup$ – Tom van der Zanden Nov 29 '15 at 15:07

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.