2
$\begingroup$

The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient algorithm to construct an $n\times n$ matrix where the entry corresponding to vertices $u$ and $v$ is the minimum weight path consisting of exactly $\alpha$ edges, or $\infty$ if no such path exists? A path is a walk that does not repeat any vertices. Assume the vertices of $G$ are numbered as $v_1,\cdots, v_n$ so that the $(i,j)$th entry of the output matrix corresponds to the min weight walk between vertices $v_i$ and $v_j$.

I know how to solve the problem when vertices can be repeated using dynamic programming, but I can't seem to solve this particular problem because vertices might be distinct.

If I ignore the condition that each such path must use exactly $\alpha$ edges, then I think the following would work, but it might be inefficient: do a breadth-first search for every possible starting vertex $s$ to find the minimum weight walk from $s$ to all other vertices. I could then store these $n$ distances for each vertex to obtain the required $n\times n$ matrix (each computation would add a new row). This would take $O(n(n+m))$ time.

The problem with using exactly $\alpha$ edges is that even though one can decompose a shortest path of length $\alpha$ between two vertices $u$ and $v$ into a shortest path of length $\alpha_1$ between $u$ and $i$ and a shortest path of length $\alpha_2$ between $i$ and $v$ for some intermediate vertex $i$, where $\alpha_1 + \alpha_2 = \alpha$. But one must check that the shortest (min weight) path of length $\alpha_1$ doesn't share a vertex other than $i$ with the shortest path of length $\alpha_2$.

Correction: BFS obviously can't be used for the shortest paths of a weighted graph, but neither Dijkstra's nor Bellman ford can be used as no vertices can repeat.

$\endgroup$

1 Answer 1

4
$\begingroup$

As you have noticed, the requirement of vertices in a path being distinct introduces significant difficulty and obstacle against an efficient algorithm.

That requirement has far-reaching impact both literally and figuratively.

Literally, each previous inclusion of a vertex in a path affects any later choice directly and independently, however distant those choices are.

Figuratively, that requirement makes this problem $\mathsf{NP}$-hard. If we have solved the special case when $\alpha=n-1$, i.e., finding the shortest path from $u$ to $v$ going through all other vertices, then we have solved Hamiltonian path problem, an $\mathsf{NP}$-hard problem. So this problem is $\mathsf{NP}$-hard as well.

In particular, people have researched intensively for decades to find a polynomial algorithm to solve Hamiltonian path problem and other $\mathsf{NP}$-complete problems. No success so far. If "an efficient algorithm" means a polynomial-time algorithm, it is safe to bet an efficient algorithm won't be found in many years. By a majority opinion of computer science community, there cannot be an efficient algorithm.

$\endgroup$
5
  • $\begingroup$ Exercise: show that the special case when $\alpha=n/10$ is also $\mathsf{NP}$-complete. $\endgroup$
    – John L.
    Mar 13 at 20:55
  • $\begingroup$ Thanks. Could you provide a formal proof for why the problem I described is indeed NP-hard? $\endgroup$ Mar 15 at 14:47
  • $\begingroup$ @FredJefferson, is my writing here good enough? $\endgroup$
    – John L.
    Mar 15 at 19:28
  • 1
    $\begingroup$ Thanks. I understand now. Basically if you can solve in polynomial time a really "hard" computational problem like DVAPSP, then you can solve a simpler decision variant in polynomial time. $\endgroup$ Mar 19 at 18:48
  • $\begingroup$ @FredJefferson. Yes, it becomes quite obvious once you have understood. $\endgroup$
    – John L.
    Mar 19 at 18:52

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.