CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Brian HK
Brian HK

Reputation: 920

NP complete Theory: Long Path

The question is basically to show that for any unweighted graph G(V,E), if we could find a simple path as big as floor(|V|/2), we could compute hamiltonian paths.

Basically that Hamiltonian Paths are polynomial time reducible to the long path problem.

I have tried to find a graph in which a path of size |v|/2 would map to another graph's Hamiltonian Path. Yet I have not gotten anywhere with that approach.

Maybe there is a way to prove there is a finite number of paths grater than length |V|/2 for any graph, which would mean we could just repeat our long path algorithm several times to find our Hamiltonian Paths. But I am not sure of this.

Upvotes: 1

Views: 598

Answers (1)

templatetypedef
templatetypedef

Reputation: 372982

As a hint, suppose that you want to find a Hamiltonian path in a graph with n nodes. What happens if you create a new graph that's two independent copies of the original graph and ask whether that new graph has a Hamiltonian path going through n nodes?

Hope this helps!

Upvotes: 1

Related Questions