11
$\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 one restricts to unit-weight graphs, that is graphs for which $w(e) = 1$ for each $e \in E(G)$?

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

1 Answer 1

Reset to default
0
$\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.

Improve this answer
$\endgroup$
2
  • 9
    $\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
  • 2
    $\begingroup$ Got it. Thank you! $\endgroup$
    – NYD
    Jun 8, 2020 at 12:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.