CODEWITHSUNDEEP
algorithmgraph-theorynpnp-completehamiltonian-path
Abhijit Sarkar
Abhijit Sarkar

Reputation: 24593

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems can be solved in polynomial time?

Hint: The Hamiltonian path problem is: given an undirected graph with n vertices, decide whether or not there is a (cycle-free) path with n - 1 edges that visits every vertex exactly once. You can use the fact that the Hamiltonian path problem is NP-complete. There are relatively simple reductions from the Hamiltonian path problem to 3 of the 4 problems below.

  • For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path exists). The path is allowed to contain cycles.
  • Amongst all spanning trees of the graph, compute one with the smallest-possible number of leaves.
  • Amongst all spanning trees of the graph, compute one with the minimum-possible maximum degree. (Recall the degree of a vertex is the number of incident edges.)
  • For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path exists). The path is not allowed to contain cycles.

Notice that a Hamiltonian path is a spanning tree of a graph and only has two leaf nodes, and that any spanning tree of a graph with exactly two leaf nodes must be a Hamiltonian path. That means that the NP-Complete problem of determining whether a Hamiltonian path exists in a graph can be solved by finding the minimum-leaf spanning tree of the graph: the path exists if and only if the minimum-leaf spanning tree has exactly two leaves. Thus, problem 2 is NP-Complete.

Problem 3 is NP-Hard; here is a paper that proves that.

That means, between 1 and 4, one is NP-Complete, another is in P. It seems like problem 4 reduces trivially to the the Hamiltonian path problem, but I'm not able to understand how having a cycle makes it solvable? Or is it the other way?

Upvotes: 0

Views: 1347

Answers (1)

Yola
Yola

Reputation: 19063

For the first one you can use Dijkstra to get shortest even and odd distances possible. To this end for every vertex you need to store not a single minimum number, but two of them. One is minimum weight of an odd path, another one is for minimum weight of an even path. After you have these two lengths you can easily increase path length by even number of edges if cycles are allowed. So, the first problem is from P. Step-be-step algorithm would be:

  1. Find shortest even and odd length paths.
  2. Increase length of one of these paths which has the same parity as n-1 to n-1 by adding cycle of length 2 required number of times.

Upvotes: 0

Related Questions