Confused on Bellman Ford

Question

We have a graph where we want to get from node u to v in the shortest path possible.

I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u to v. But how does this work when you have to go from u to v with at least k number of edges?

Is this a simple variation of bellman-ford or is there more to this problem?

So far my reading material has been: DPV, Wikipedia, and online publications

Would someone be able to shed some light on this topic?

Thanks.

Answer 1

Consider the following problem:

Given an undirected, weighted graph $G=(V,E)$, and a pair of vertices $s,t$, we wish to find a lowest cost path from $s$ to $t$ with length exactly $k$. That is, out of all paths from $s$ to $t$ with length $k$, we wish to find the one with the lowest cost.

As D.W tried to direct you towards, Hamiltonian Path is reducible to this problem. w.l.g, we can set all weights to be 1, and set $k$ to be $n-1$ (assuming the length $k$ defines the number of edges in the path), then if we have a solution to the problem above, the same solution with these properties would find a Hamiltonian path, thus the problem is NP-Hard.

For completeness, and since you articulated that you are interested in a path with at least $t$ edges, we can also find the necessary reduction by solving this problem for all $k$ between $t\dots n-1$.

---

Note that, if you don't require the path to be $\mathit{simple}$, you can find the answer in polynomial time by some form of DP or duplicating the graph $k$ times.