
Recent Posts
 Hitting String April 26, 2017
 Bounded Post Correspondence Problem April 19, 2017
 Shortest Common Superstring April 12, 2017
 Shortest Common Supersequence April 7, 2017
 Longest Common Subsequence March 29, 2017
Recent Comments
Archives
 April 2017
 March 2017
 February 2017
 January 2017
 December 2016
 November 2016
 October 2016
 September 2016
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
Categories
Meta
Tag Archives: Hamiltonian Path
Protected: 3Matroid Intersection
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3Matroid Intersection, 3DM, Difficulty 8, Hamiltonian Path, No G&J reference, SP11
Protected: Kth Shortest Path
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 5, Hamiltonian Path, kth shortest path, ND31, Turing Reduction, uncited reduction
Protected: Isomorphic Spanning Tree
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 2, Hamiltonian Path, Isomorphic Spanning Tree, ND8, No G&J reference, uncited reduction
Protected: Maximum Leaf Spanning Tree, Connected Dominating Set
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 2, Difficulty 5, Dominating Set, Hamiltonian Path, ND2, No G&J reference, Not in Appendix, uncited reduction, Vertex Cover
Protected: Degree Constrained Spanning Tree
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Degree Constrained Spanning Tree, Difficulty 1, Hamiltonian Path, ND1, No G&J reference, uncited reduction
Protected: Hamiltonian Completion
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged Difficulty 1, Difficulty 2, GT33, Gt34, Hamiltonian Circuit, Hamiltonian Completion, Hamiltonian Path, No G&J reference, uncited reduction
Protected: Hamiltonian Path on Bipartite Graphs
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged Difficulty 5, Hamiltonian Circuit, Hamiltonian Path, Hamiltonian Path on Bipartite Graphs, Not in Appendix
Protected: DegreeBounded Connected Subgraph
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged DegreeBounded Connected Subgraph, Difficulty 2, GT26, Hamiltonian Path, uncited reduction
Protected: Longest Path
Enter your password to view comments.
Posted in Chapter 3 Exercises
Tagged Difficulty 1, Hamiltonian Path, Longest Path, ND29, No G&J reference, reductions, restrictions, uncited reduction
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 <v_{1}, v_{2}…v_{n}>of the vertices where an edge exists between each (v_{i}, v_{i+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 G_{HC}, an instance of HC, we build G_{HP} to be the exact same graph with 2 vertices added v_{start} and v_{end}. We add two edges, one from v_{start} to some vertex in G_{HC}, and one from v_{end} to the same vertex in G_{HC}. The idea is that a Hamiltonian path in this graph would start at v_{start}, travel through the HC in the given graph (if it exists), and end at v_{end}.
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 differentlooking 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)