0
$\begingroup$

Task:
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, the 1/2 hamiltion path problem (1/2-HPP) asks for a path that visits exactly half of the nodes.
Show that: $HPP \le_{P} 1/2-HPP$

Question: Can anyone give me a hint on how to prove $HPP \le_{P} 1/2-HPP$

$\endgroup$
0
$\begingroup$

Double the graph size: make two clones of the input $G_1,G_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G_1,G_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G_1$ or all $G_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.

$\endgroup$
1
$\begingroup$

You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.

$\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.