# Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This generates problems as suggested here: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs Anyone can give a hint on how to make a bipartite graph from a general one without using the above method and how the hamiltonian property can be passed to it?

## 3 Answers

Given $G = (V,E)$, define $\tilde{G} = (\tilde{V},\tilde{E})$ by adding vertices $i^+$ and $i^-$ to $\tilde{V}$ for each $i\in V$ and edges $i^-j^+$ and $i^+j^-$ for each edge $ij\in E$.

It's not too hard to check that if $|V|$ is odd, $G$ has a Hamiltonian cycle if and only if $\tilde{G}$ is. If $|V|$ is even, just add one new vertex of degree 2 with neighbors that have an edge between them.

So far, we've seen that Hamiltonian Cycle in bipartite graphs is hard. To reduce this to Hamiltonian Path, just continue in the way you normally would to reduce Hamiltonian Cycle to Hamiltonian Path.

• Louis, i think that what you proposed here indeed creates a bipartite graph (with two independent sets - one with the (+) vertexes and one with the (-) vertexes - really smart) but does not quarantee the Hamilton Path (i want Path and not Cycle) in the new graph. For instance take the graph with edges (a,b),(b,c). These two edges are also the HP in this graph (and it also has odd #vertices-(3)) but the new graph constructed by the method you proposed does not produce any HP at all...
– John
Nov 26 '13 at 17:06
• This is for Hamiltonian cycles. To get to a path, use a standard reduction. Nov 26 '13 at 17:15
• Well, standard is what i am looking for! Let's say can i somehow prove that HP(in bypartite graphs) <= HC(in bypartite graphs)). With your proof, this ends it. But the above proof is different than in simple graphs where i add a new vertex and connect every other vertex with it - it gives a 3-colored graph...
– John
Nov 26 '13 at 17:24
• I am stuck in the proof (for the HC in bipartite graphs): lets say i have a Ham. cycle: i->j->k->...->i, this can become a Ham. cycle in the new G like this: i(-)->j(+)->k(-)->...->i(+)->j(-)->k(+)->...->i(-) by using the rules for constructing the new bipartite G. How can i prove the opposite direction?
– John
Nov 26 '13 at 19:52
• Also when you say: "If |V| is even, just add one new vertex of degree 2 with neighbors that have an edge between them" -> if you mean to delete that edge and add the two others then this generates a problem in the proof because edges that are not in the Hamilton Cycle of the first graph produce vertices that are not traversed in the HC of the second (bipartite one)...
– John
Nov 26 '13 at 20:02

I actually found a solution (one that I could understand completely and explain). I want to prove that HP on bipartite graphs is NP-complete.

1. Firstly, I prove that HC on bipartite graphs is NP-complete (reduction from HC on digraphs): From $$G=(V,E)$$ construct $$G'=(V',E')$$ as follows: replace each vertex $$u$$ with 4 others instead: $$u_{in},u_{mid,1},u_{mid,2},u_{out}$$ and apply the 3 consecutive edges between those vertices. Also for each $$(u,v)$$ in $$E$$ there will be an undirected edge $$(u_{out},u_{in})$$ in $$E'$$. So $$G'$$ is bipartite (since all vertices $$u_{in}$$ and $$u_{mid,2}$$ are one independent set and the rest are the other). Going from a cycle in $$G$$ to a cycle in $$G'$$ is very clear now and much more easier to understand.
2. Secondly, I prove that HP on bipartite graphs is NP-complete (reduction from HC on bipartite graphs): From $$G$$ construct $$G'$$ as follows: add a $$w$$ vertex and an edge $$(w,u)$$, where $$u$$ is a vertex in $$V$$. Add a vertex $$x$$. For every $$v$$ in $$Γ(u)$$ (every neighboor of $$u$$) add edge $$(v,x)$$. Add vertex $$y$$ and connect it to $$x$$ (edge $$(x,y)$$). Now the $$G'$$ is bipartite (since $$x,u$$ belong to the same independent set and $$y,w$$ to the other one). The proof afterwards is easy, since we can observe that a HP on $$G'$$ will have the edge $$(y,x)$$ and also $$(x,v), v \in Γ(u)$$.

If a bipartite graph has an odd number of vertices then it is proven that it is non-Hamiltonian thus it is not a HC. The proof is in the pdf here: http://www.cs.helsinki.fi/u/polishch/pages/teaching/solutions03.pdf

Now I think for the HC with even number of vertices, you just do the known reduction from the HP we have done in class. I'm not quite sure about this though.

Also, I found this. Maybe it helps you maybe not. It has the proof from a directed HC to undirected HC. http://classes.soe.ucsc.edu/cmps201/Fall09/Handouts/ho11-hc-dir.pdf

Also you can check this out: http://courses.cs.tau.ac.il/cc/02a/exercises/ex04_ans.pdf question 4

Also maybe Reza Zamani Nasab's thesis will help you.

• A bipartite graph with an odd number of vertices cannot have a Hamiltonian cycle but the question asks for Hamiltonian paths. A path with an odd number of vertices is bipartite but still has a Hamiltonian path. Nov 28 '13 at 17:38