0
$\begingroup$

Suppose we are given that checking if there is a Hamiltonian path in a graph is NP Complete (HP problem). I want to prove that given a graph, node x, and node y, checking if there is a Hamiltonian path between x and y is NP Hard (HPN problem). Here is my proof:

Define a conversion from HP to HPN as follows:

result = False for x in Nodes(G): for y in Nodes(G): result = result or hpn(G,x,y) return result

This clearly solves the HP problem since it considers all possible starting and ending points. Also, HPN is called a polynomial (O(|Nodes(G)|^2) number of times. Hence, HPN must be NP-Hard since if it wasn't HP wouldn't be NP Complete and we know that this isn't true.

I understand I haven't used a reduction in the formal sense in my proof. However, I wanted to know if these sorts of "conversions" are valid in proving NP Hardness/Completeness.

Edit : The goal was actually to prove NP hardness, not completeness, sorry!

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    May 7 '19 at 16:00
  • 2
    $\begingroup$ This is a Turing reduction, which is weaker than a Karp reduction we usually look for. $\endgroup$
    – Juho
    May 7 '19 at 16:18
1
$\begingroup$

No, they're not. NP-completeness is defined using many-one reductions and you've used a Turing reduction. The difference, in a nutshell, is that for a many-one reduction, you're only allowed to make one call to the function you've called hpn, and you must return its result as your result. Schematically, your reduction needs to look like:

Compute a graph G' and vertices x and y from the input graph G;
return hpn(G',x,y);
Improve this answer
$\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.