2
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ Try the graph a-b, b-c, c-d, d-a, a-c by hand. $\endgroup$
    – zxc
    Apr 24, 2012 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, 2012 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, 2012 at 22:22

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

Here's a graphic illustration of the problem after changing the diagonal line with edge-vertex-edge there isn't a Ham-Cycle

enter image description here

Improve this answer
$\endgroup$
-2
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.