0
$\begingroup$

Wikipedia link states that you are able to reduce HP to HC by adding a single vertex that is connected with all the edges. I understand the reason why the reduction from cycle to path works by adding 2 vertices, one connected to s and the other to t.

The problem is, I can't seem to find or come up with a solution for why this reduction is wrong or incomplete:

Given a directed graph G with a hamiltonian path from s to t, convert it into a graph H that contains a hamiltonian cycle, by just adding one edge from t to s.

It seems correct at first glance but my professor said that it is incorrect in computation complexity terms and I can't find out why.

$\endgroup$
1
$\begingroup$

Adding a vertex $x$ to an existing graph $G$ and connecting it to all the vertices in $G$ (calling the new graph $H$) works in general: any Hamiltonian cycle in $H$ corresponds to a Hamiltonian path in $G$. So if you can find a Hamiltonian cycle in $H$, this immediately gives you a Hamiltonian path in $G$, and if there are no Hamiltonian cycles in $H$ then there are no Hamiltonian paths in $G$. Hence the conclusion that "finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle."

Your suggestion of connecting two ends of a Hamiltonian path in $G$ to form $H$ would indeed lead to your $H$ having a Hamiltonian cycle. But it involves finding the ends of the Hamiltonian path in $G$ first before you even know the existence of $H$. The quoted conclusion is based on the other direction: it points to how finding a Hamiltonian cycle in its $H$ leads easily to finding a Hamiltonian path in $G$

$\endgroup$
1
$\begingroup$

Think about the reason why you consider reductions: You have one problem that needs a solution (HP, Hamiltonian Path), but you can solve a similiar one (HC, Hamiltonian Cycle).

If you can transform your problem (HP) to the other one (HC), you can solve that and from the solution for HC solve your problem (HP).

But in your example, you already have crucial information about your problem, you somehow know the end points of the Hamiltonian path ($s$ and $t$). That's "cheating", that's not the original problem of finding a Hamiltinion Path!

What you can do, is to argue: "If there is a Hamiltonian Path in my graph, the end points may be connected by an edge in the graph, or they are not connected. A Hamiltonian Path of the first kind can easily be found by looking for a Hamiltonian Cycle in the graph. If I find one, I can of course easly find a Hamiltonian Path in my graph."

"If I don't find such a Hamiltonian Cycle, I take every pair of graph vertices $(v_1,v_2)$ that are not connected by an edge in my graph, and produce from it the graph where I add an edge between $v_1$ and $v_2$. I look for a Hamiltonian Cycle in that graph, and if I find one, I can easily make a Hamiltonian Path from it in my original graph (starting/ending at $v_1,v_2$). If I find no Hamiltonian Cycle in any such graph, there can't be a Hamiltonian Path in the original graph!".

To that your Profesor might reply:

"You are correct, that works. Here take this graph with 20 vertices and 40 edges. There are ${20 \choose 2}=190$ vertex pairs, 40 edges exist already in the graph, so you need to consider $150$ vertex pairs in your algorithm. Use that computer program I gave you to solve the Hamiltonian Cycle problem for those 151 graphs (don't forget the original one) with 20 vertices and 40 or 41 edges. Tell me your result. Class meets tomorrow at 8am. See you!"

At this point it may dawn on you that while you provided a working reduction, it is a rather inefficient one if you don't know the starting/ending points of your Hamiltonian Path! Your classmates, who use the wikipedia solution, just need to solve one Hamiltonian Cycle problem, for a graph with 21 vertices and 60 edges.

Tl,dnr: You initially 'cheated' by assuming you already know the starting/ending points of the Hamiltonian Path. Your idea can be expanded to a full reduction, it is just an 'inefficient' one.

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