I'm trying to solve a problem for class that is stated like so:

A bipartite graph is an undirected graph in which every cycle has even length. We attempt to show that the Hamiltonian cycle (a cycle that passes through each node exactly once) problem polynomially reduces to the Hamiltonian cycle problem in bipartite graphs. We need a function $T: \{\text{graphs}\} \to \{\text{bipartite graphs}\}$ such that $T$ can be computed in polynomial time and for any graph $G$, $G$ has Hamiltonian cycle iff $T(G)$ has a Hamiltonian cycle. Let $T(G)$ be the bipartite graph obtained by inserting a new vertex on every edge. What is wrong with this transformation?

I think the problem with the transformation is that for $T(G)$ you need to insert an edge between each pair of vertices and not just insert a new vertex on every edge. I'm actually a bit stumped by this one. Any advice would be much appreciated!

  • $\begingroup$ Try the graph a-b, b-c, c-d, d-a, a-c by hand. $\endgroup$ – zxc Apr 24 '12 at 0:16
  • $\begingroup$ This problem doesn't make sense. How do you put a new vertex on every edge? A new vertex z s.t. if x->y, then x->z->y? $\endgroup$ – spinning_plate Apr 24 '12 at 0:16
  • $\begingroup$ spinning_plate gives a hint for a working transformation: “how can you make a bipartite graph from an arbitrary graph?” $\endgroup$ – Gilles 'SO- stop being evil' Apr 27 '12 at 22:22

The problem is that a Hamiltonian cycle has to pass through all vertices: if the cycle in the original graph does not take some edge $e$, then the vertex you split $e$ with will not be taken if you take the same route. This means that the resulting cycle is not Hamiltonian.


Is it possible that the transformation is correct but pointless? Consider Barnette's conjecture:

If a planar graph is bipartite and cubic but only 2-connected, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs.

(possibly taken out of context - check back with the Wikipedia entry). Is it possible that all you are doing is reducing one known NP-complete problem to another known NP-complete problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy