# The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem

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.

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.

• Exercise: show that the special case when $\alpha=n/10$ is also $\mathsf{NP}$-complete. Mar 13 at 20:55
• Thanks. Could you provide a formal proof for why the problem I described is indeed NP-hard? Mar 15 at 14:47
• @FredJefferson, is my writing here good enough? Mar 15 at 19:28
• 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. Mar 19 at 18:48
• @FredJefferson. Yes, it becomes quite obvious once you have understood. Mar 19 at 18:52