2
$\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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ For the PS: yes, it does include Hamiltonian Path Problem as a subproblem. $\endgroup$ Commented Apr 9, 2019 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$ Commented Apr 9, 2019 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$ Commented Apr 9, 2019 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$ Commented Apr 9, 2019 at 17:57

1 Answer 1

Reset to default
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})$$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.