HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
paththegraphexistencebipartitecompletethathamiltonproof

Problem

I tried to solve the exercise:

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

by making a bipartite graph from a general one (undirected) by inserting a vertex 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
Can anyone 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?

Solution

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.

Context

StackExchange Computer Science Q#18335, answer score: 3

Revisions (0)

No revisions yet.