1
$\begingroup$

I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s to vertex t using at least k edges but less than 20. No vertex may be repeated in a path.

I am aware of this problem: Dijkstra's algorithm to compute shortest paths using k edges?

That problem wants to find the shortest paths using at most k edges.

My current idea is to create the product graph via V' = V x {0, 1, 2, ..., 20} and then ignore any shortest paths from (s, 0) to (t, n) where n < k. However, because the product construction essentially duplicates nodes, I am not aware of a way to ignore duplicate vertices in the path-finding algorithm.

P.S. If k were very large, say, k = |V|, wouldn't this be the Hamiltonian path problem and therefore NP-complete?

$\endgroup$
  • 3
    $\begingroup$ For the PS: yes, it does include Hamiltonian Path Problem as a subproblem. $\endgroup$ – John Dvorak Apr 9 at 17:10
  • $\begingroup$ @John Dvorak the linked problem gave a worst case complexity of 𝑂(𝑘⋅(|𝑉|+|𝐸|)lg|𝐸) and it includes the Hamiltonian Path Problem if k = |V| and there are no paths for k less than this. Am I mistaken? $\endgroup$ – cs questions Apr 9 at 17:46
  • 1
    $\begingroup$ @csquestions, if you are not allowed cycles, then this is NP-complete. See this question, specifically the first and last bullet point. Also see last paragraph of this answer to that question. $\endgroup$ – ryan Apr 9 at 17:52
  • 1
    $\begingroup$ if you allow cycles, then you can either replicate the graph $k$ times, or apply some dynamic programming approach. Since you don't, it's NP-complete $\endgroup$ – lox Apr 9 at 17:57
2
$\begingroup$

Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice.

Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in polynomial time for $k=n-1$ and thus find a path that visits eeach vertex in $V$ exactly once. In other words, we can "solve" Hamiltonian Path.

If you know in advance that $k \leq 20$ then you can exhaustive search all paths of length at most 20, and therefore solve for small $k$.

An exhaustive search, at worst, is to search every vertex order starting from $s$ that ends in $t$ (corresponding to existing edges), so in total you will search: $$(n-1)(n-2)(n-3)...(n-20) = O(n^{20})$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.