-2
$\begingroup$

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.

$\endgroup$
4
  • 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$ Nov 28, 2015 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$ Nov 28, 2015 at 17:32
  • $\begingroup$ Are you assuming you can multiply large numbers in constant time? $\endgroup$ Dec 7, 2015 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$ Dec 11, 2015 at 14:43

1 Answer 1

-3
$\begingroup$

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.

$\endgroup$
20
  • 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, 2015 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, 2015 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, 2015 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$ Nov 29, 2015 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$ Nov 29, 2015 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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