[Based on a puzzle given to me by Anand Ganesh]
Determining whether a connected graph G has a Hamiltonian Path is NP-Complete.
A little known fact is that determining if the square of a connected graph G has a Hamiltonian Path is also NP-Complete. In the square of G, two vertices are adjacent iff they are at a distance at most two in G.
This post is about the cube (distance at most three) of a connected graph.
It can be shown that the cube of any connected graph always contains a Hamiltonian Path, and there is a simple proof of that, which demonstrates the power of using a stronger induction hypothesis.
It is enough to prove that the cube of a tree is Hamiltonian, as given a graph, we can just consider a spanning tree.
Given a tree, assume it is a rooted tree (pick an arbitrary vertex as the root), so we can talk about children and parents etc. Now we try to arrange the vertices of the tree as v1,v2,…,vn such that the distance between vk and vk+1 is at most three (i.e. v1,v2,…,vn is a Hamiltonian Path in the cube of the graph).
We now use the following induction hypothesis:
Proposition: The n≥2 vertices of a rooted tree T can be arranged as v1,v2,…,vn such that vk and vk+1 are at a distance at most three in T, and (this where we make the hypothesis stronger) v1 is the root, and vn is a child of the root.
Now if the root has s sub-trees, we get the arrangements for the sub-trees (using the induction hypothesis), concatenate them, put the root at the end and reverse the resulting arrangement.
The resulting arrangement has the root as the first vertex, and a child of the root as the last. It is also easy to verify the distance at most three requirement: the distance between any child and any grand-child (possibly a child of a different child) is at most three.
This inductive proof can also be converted to a linear time algorithm for finding a Hamiltonian path in the cube of a graph.
Note that while trying to prove the property about Hamiltonian paths, we basically ended up proving the property about Hamiltonian cycles.
Related reading: http://en.wikipedia.org/wiki/Graph_power
Determining whether a connected graph G has a Hamiltonian Path is NP-Complete.
A little known fact is that determining if the square of a connected graph G has a Hamiltonian Path is also NP-Complete. In the square of G, two vertices are adjacent iff they are at a distance at most two in G.
This post is about the cube (distance at most three) of a connected graph.
It can be shown that the cube of any connected graph always contains a Hamiltonian Path, and there is a simple proof of that, which demonstrates the power of using a stronger induction hypothesis.
It is enough to prove that the cube of a tree is Hamiltonian, as given a graph, we can just consider a spanning tree.
Given a tree, assume it is a rooted tree (pick an arbitrary vertex as the root), so we can talk about children and parents etc. Now we try to arrange the vertices of the tree as v1,v2,…,vn such that the distance between vk and vk+1 is at most three (i.e. v1,v2,…,vn is a Hamiltonian Path in the cube of the graph).
We now use the following induction hypothesis:
Proposition: The n≥2 vertices of a rooted tree T can be arranged as v1,v2,…,vn such that vk and vk+1 are at a distance at most three in T, and (this where we make the hypothesis stronger) v1 is the root, and vn is a child of the root.
Now if the root has s sub-trees, we get the arrangements for the sub-trees (using the induction hypothesis), concatenate them, put the root at the end and reverse the resulting arrangement.
The resulting arrangement has the root as the first vertex, and a child of the root as the last. It is also easy to verify the distance at most three requirement: the distance between any child and any grand-child (possibly a child of a different child) is at most three.
This inductive proof can also be converted to a linear time algorithm for finding a Hamiltonian path in the cube of a graph.
Note that while trying to prove the property about Hamiltonian paths, we basically ended up proving the property about Hamiltonian cycles.
Related reading: http://en.wikipedia.org/wiki/Graph_power
No comments:
Post a Comment