I know there is this solution for Karp reduction from HC to HP in here (INDIRECTED graph).
But I was thinking about something else, and would like to know what you think about it.
I create 2 new vertices, v' and u', and connect them with v and u (v' to v and u' to u), where v and u are vertices in the old graph, which are connected directly with an edge.
Instead of getting confused with too many words, I will show an image of how I want to build my reduction.
The build itself is in red.
Is my reduction wrong? Can you give me an example where this reduction fails?
(The image is just an example, I tried it on many graphs and it worked on all of them)
Edit: To make things clearer:
I need to find a Karp reduction from "Hamiltonian Cycle" to "Hamiltonian Path".
A Hamiltonian cycle is a closed loop on a graph where every node (vertex) is visited exactly once
A Hamiltonian path, is a graph path between two vertices of a graph that visits each vertex exactly once
I suggest the following:
Take an arbitrary vertex v. it is promised it has a neighbor u because it is an HC.
For v, connect an edge from it to v' (a new vertex), and for u connect an edge from it to u' (a new vertex).
I claim this reduction is from HC to HP.
Why?
Lets assume this is an HC. That means I can go from anywhere to anywhere in the graph. If I build v' and u', that means they are the only vertices with degree of 1, and that means I can either start/finish from one of them to one of them. Hence, a directed path.
Lets assume this is an HP (after building). That means I can go from one vertex to another by traversing each vertices exactly once. Because it is guaranteed by building that v' and u' are the only ones with rank of 1, I will start/finish with them. It is also guaranteed that each one of them is connected to v/u, and it is known that v and u are connected with an edge, and there is a path between them regardless of their shared edge. Hence, if I remove v', u' and their built edges, I can go from u to v in two directions, and visit every vertex exactly once, besides u or v. And that is why it is an HC.
Best Answer
Your reduction appears to be the same as the one in Aryabhata's answer to the question
$\;\;\;\;\;$ Reduction from Hamiltonian cycle to Hamiltonian path
as referenced in your post.
However it's not guaranteed that with the first chosen edge $uv$, your proposed reduction yields a Hamiltonian path. Thus, for the reduction to succeed, for a fixed choice of $v$, you would need to iterate the HP algorithm over all edges $uv$ until one such choice yields a Hamiltonian path.
Hence, since the reduction requires multiple applications of HP, it's a Cook reduction, not a Karp reduction.
Nevertheless, for each fixed choice of $v$, there are at most $n-1$ edges $uv$, hence the reduction shows that HC is polynomial-time reducible to HP.
But note:
I don't see the need for the $u',v'$ construction.
Instead, choose a vertex $v$ of least degree, and for each neighbor $u$ of $v$, just delete the edge $uv$ and apply an HP algorithm to the reduced graph. If it succeeds, just reconnect $uv$. If there is a Hamiltonian cycle, there will be at least two neighbors $u$ of $v$ for which the HC algorithm on the reduced graph will work.