[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 \(v_1, v_2, \dots, v_n\) such that the distance between \(v_k\) and \(v_{k+1}\) is at most three (i.e. \(v_1, v_2, \dots, v_n\) is a Hamiltonian Path in the cube of the graph).
We now use the following induction hypothesis:
Proposition: The \(n \ge 2\) vertices of a rooted tree \(T\) can be arranged as \(v_1, v_2, \dots, v_{n}\) such that \(v_k\) and \(v_{k+1}\) are at a distance at most three in \(T\), and (this where we make the hypothesis stronger) \(v_1\) is the root, and \(v_n\) 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 \(v_1, v_2, \dots, v_n\) such that the distance between \(v_k\) and \(v_{k+1}\) is at most three (i.e. \(v_1, v_2, \dots, v_n\) is a Hamiltonian Path in the cube of the graph).
We now use the following induction hypothesis:
Proposition: The \(n \ge 2\) vertices of a rooted tree \(T\) can be arranged as \(v_1, v_2, \dots, v_{n}\) such that \(v_k\) and \(v_{k+1}\) are at a distance at most three in \(T\), and (this where we make the hypothesis stronger) \(v_1\) is the root, and \(v_n\) 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