In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:

Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in $V(G)$. Let $p_1$ be a path of minimum weight from $u$ to $v$. Compute a simple path $p_2$ from $u$ to $v$ with $w(p_2) > w(p_1)$ and such that for any other path $p$ from $u$ to $v$ with $w(p) > w(p_1)$, we have $w(p) \ge w(p_2)$.

They prove that this problem is NP-hard. Their proof involves choosing a weight function that takes value $1$ on a certain edge and $0$ elsewhere, so it relies in a fundamental way on the possibility of there being edges of weight $0$.

Is anything known about whether the problem remains NP-hard when restricted to unweighted digraphs, that is directed graphs for which $w(e) = 1$ for each $e \in E(G)$?

EDIT: The variant in undirected graphs, and the variant where the goal is to find a (not-necessarily simple) walk (as opposed to a path), are known to be in P. Here's a summary:

graph type edge weights path or walk? result paper
directed non-negative path NP-hard [1997]
either non-negative walk in P [1997]
DAG non-negative path = walk in P [1997]
undirected non-negative path in P [2004, 2006, 2011, 2012a,b]
directed strictly positive path open [2011,2015]

(Note that there is also a separate body of work on fast algorithms for finding $k\ge 2$ shortest paths, e.g. [1998], where distinct path lengths are not required.)

  • 2
    $\begingroup$ We call those unweighted graphs $\endgroup$ Jun 5, 2020 at 3:51
  • $\begingroup$ My first intuition is certainly naive. What's wrong with it? Since $p_2$ is different from $p_1$ on at least one edge, repeatedly remove one edge in $p_1$ from the graph and solve the shortest path problem, which would be at worst $n$ times the complexity of the shortest path problem. $\endgroup$
    – NYD
    Jun 8, 2020 at 12:09
  • $\begingroup$ And how do you proceed, if all resulting paths have the same weight $w(p_1)$ as the original shortest path $p_1$? $\endgroup$
    – Gamow
    Jun 8, 2020 at 12:56
  • 3
    $\begingroup$ This paper solves the unweighted problem in $O(n^2)$: A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs $\endgroup$
    – isaacg
    Nov 10, 2020 at 17:24
  • 1
    $\begingroup$ In the Conclusion section of paper referred in the comment of isaacg the authors say: "the time-complexity of the next-to-shortest path problem in digraphs when the edge lengths are required to be strictly positive is still open." $\endgroup$ Mar 9, 2021 at 0:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.