Hamiltonian Path

Before I start doing my own problems where G&J don’t give proofs, here’s a really simple extension of Hamiltonian Circuit that will be useful.

The problem: Hamiltonian Path

The description: Given a graph G=(V,E), where |V| = N.  Can I create an ordering <v1, v2…vn>of the vertices where an edge exists between each (vi, vi+1) in the sequence?

(This is the Hamiltonian Circuit problem without the restriction that I return to the start)

EDIT 4/24/15.  My original reduction doesn’t work.  I’ve left it below.  Thanks to Fernando Berzal for pointing it out to me.  I’ve added his answer, which looks correct.

In all honesty, the best part about being wrong is that it means people actually read these things!

The new Reduction: From HC.  Given a graph G =(V,E), an instance of HC, pick any vertex v.

We’re going to build a graph G’ =(V’, E’)

V’ = All of the vertices in V, plus a new vertex v’ (which is a “copy” of v)

E’ = All of the edges in E, plus an edge (v’, w) if there was an edge (v,w) in E.

So, G’ is G, with one vertex (v) “duplicated” as v’.  v’ has edges to all of the places v has.

We want to see if there’s an HP from v to v’.

If G’ has an HP from v to v’, then the last edge in the path goes from some vertex u to v’.  If we replace that edge with the edge (u,v) we get a HC in G.

If G has an HC, then we can follow that cycle starting from v.  Instead of the last edge coming back to v, follow it to v’.  This will give us a HP in G’

My reduction that doesn’t work: From HC.  Given a graph GHC, an instance of HC, we build GHP to be the exact same graph with 2 vertices added- vstart and vend. We add two edges, one from vstart to some vertex in GHC, and one from vend to the same vertex in GHC.  The idea is that a Hamiltonian path in this graph would start at vstart, travel through the HC in the given graph (if it exists), and end at vend.

This doesn’t work because if the two new vertices both connect to the same vertex then we hit it twice in our HP, which breaks the rules.

Difficulty: 2.  This is a good “simple reduction” for students to work on.  I don’t use it because it’s just a variant on the same problem, and I like to drive home how reductions tie very different-looking problems together.  But I do like how it’s simple, but does make you make some changes to the original problem.

(I think that I’m going to upgrade this difficulty to 4 now, since I can see a lot of students making the same mistake I did)

2 responses to “Hamiltonian Path

  1. Dave Burchill

    in the new reduction how do you know that the HP found will be from v to v’, what if there are other HPs in G’. You could add a vertex v” and an edge (v”, v’), that way v” must be the start of any HP as it only has outgoing edges. I’m not sure what the edge (v’, w) is for maybe it addresses this in someway I don’t see right now.

  2. There are _lots_ of edges from v’ to w, one for each edge incident on v.

    I guess you can think of this as a reduction to “HP with designated endpoints”, but it’s pretty easy to go from there to regular HP.

Leave a Reply

Your email address will not be published. Required fields are marked *