13
$\begingroup$

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.)

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ We call those unweighted graphs $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented 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
    Commented 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
    Commented 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
    Commented 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$
    – Andras Farago
    Commented Mar 9, 2021 at 0:25

0

Reset to default

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.