patternMinor
Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete
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?
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.
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.