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

Question

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?

Answer 1

Problem 1 can be solved in polynomial time. Here is a simple algorithm to compute it in $O(n^2 + nm)$ (it can probably be done faster).

This can be solved in a dynamic programming style. If we find the shortest length $k$ path to all nodes from source $s$, then we can easily find the shortest length $k+1$ path to all nodes from source $s$. Let $d_k(v)$ be the length of the shortest $k$-length path to node $v$ from source $s$. We have:

$$d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$$

Where $d_0(s) = 0$ and $d_0(v) = \infty$ if $v \neq s$. Then we must simply iterate over all $k$ and compute the necessary values.

set d(s) = 0
set d(v) = infty for all v != s
for k in 1, 2, ..., n-1 do:
  for all nodes v do:
    set dp(v) = infty
    for all nodes u adjacent to v do:
      set dp(v) = min(dp(v), d(u) + w(u,v))
  set d = dp
return d(t)

Note that dp is just an intermittent variable so that $d_k$ is correctly computed on $d_{k-1}$ rather than accidentally overwriting $d_{k-1}$.

The two inner for loops take $O(n + m)$ and the outer takes $O(n)$. Overall this algorithm takes $O(n^2 + nm)$.

The reason for this speed-up is precisely what Peter said. We do not need to keep track of intermediate nodes in order to prevent cycles, we simply keep going without worry of cycles at all. If we needed to keep track of intermediate nodes then it is not necessarily the case that $d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$. It may end up being that case that we would actually not use $d_k(u)$ to compute $d_{k+1}(v)$ because there may be a slightly longer path to $u$ that actually allows us to use edge $(u,v)$. This creates a combinatorial explosion in terms of what we must check and remember.

Answer 2

I'm not able to understand how having a cycle makes it solvable?

The basic intuition is that it reduces the amount of state you need to track. With cycles allowed you just need to build up a table of the shortest length-k path from s to each other vertex. With cycles disallowed you need to track all of the intermediate vertices, so you potentially wind up with a table of all path prefixes.

Answer 3

Problem 1 seems indeed P to me.

What about an algorithm based on Bellman-Ford doing exactly n-1 steps ? The trick would be that on each step you take for every node the minimum incoming path without comparing to the last step value (if there is no incoming path, put a +inf again).