<p>In the paper &quot;Computing strictly-second shortest paths&quot; (1997), Lalgudi and Papaefthymiou consider the following problem:</p>
<blockquote>
<p>Let <span class="math-container">$G$</span> be a directed graph with edge-weighting <span class="math-container">$w$</span>. Let <span class="math-container">$u,v$</span> be vertices in <span class="math-container">$V(G)$</span>. Let <span class="math-container">$p_1$</span> be a path of minimum weight from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>. Compute a <em>simple</em> path <span class="math-container">$p_2$</span> from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> with <span class="math-container">$w(p_2) &gt; w(p_1)$</span> and such that for any other path <span class="math-container">$p$</span> from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> with <span class="math-container">$w(p) &gt; w(p_1)$</span>, we have <span class="math-container">$w(p) \ge w(p_2)$</span>.</p>
</blockquote>
<p>They prove that this problem is NP-hard. Their proof involves choosing a weight function that takes value <span class="math-container">$1$</span> on a certain edge and <span class="math-container">$0$</span> elsewhere, so it relies in a fundamental way on the possibility of there being edges of weight <span class="math-container">$0$</span>.</p>
<p>Is anything known about whether the problem remains NP-hard when restricted to unweighted digraphs, that is directed graphs for which <span class="math-container">$w(e) = 1$</span> for each <span class="math-container">$e \in E(G)$</span>?</p>
<hr />
<p><em>EDIT:
The variant in undirected graphs,
and the variant where the goal is to find a (not-necessarily simple) <em>walk</em> (as opposed to a path),
are known to be in P.  Here's a summary:</em></p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th style="text-align: center;">graph type</th>
<th style="text-align: center;">edge weights</th>
<th style="text-align: center;">path or walk?</th>
<th style="text-align: center;">result</th>
<th style="text-align: center;">paper</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;">directed</td>
<td style="text-align: center;">non-negative</td>
<td style="text-align: center;">path</td>
<td style="text-align: center;">NP-hard</td>
<td style="text-align: center;">[1997]</td>
</tr>
<tr>
<td style="text-align: center;">either</td>
<td style="text-align: center;">non-negative</td>
<td style="text-align: center;"><strong>walk</strong></td>
<td style="text-align: center;">in P</td>
<td style="text-align: center;">[1997]</td>
</tr>
<tr>
<td style="text-align: center;"><strong>DAG</strong></td>
<td style="text-align: center;">non-negative</td>
<td style="text-align: center;">path = walk</td>
<td style="text-align: center;">in P</td>
<td style="text-align: center;">[1997]</td>
</tr>
<tr>
<td style="text-align: center;"><strong>undirected</strong></td>
<td style="text-align: center;">non-negative</td>
<td style="text-align: center;">path</td>
<td style="text-align: center;">in P</td>
<td style="text-align: center;">[2004, 2006, 2011, 2012a,b]</td>
</tr>
<tr>
<td style="text-align: center;">directed</td>
<td style="text-align: center;"><strong>strictly positive</strong></td>
<td style="text-align: center;">path</td>
<td style="text-align: center;">open</td>
<td style="text-align: center;">[2011,2015]</td>
</tr>
</tbody>
</table></div>
<p>(Note that there is also a separate body of work on fast algorithms for finding <span class="math-container">$k\ge 2$</span> shortest paths, e.g. [1998], where distinct path lengths are not required.)</p>
<hr />
<ul>
<li><p>[1997] <em>Lalgudi, Kumar N.; Papaefthymiou, Marios C.</em>, <a href="https://doi.org/10.1016/S0020-0190(97)00122-1" rel="nofollow noreferrer"><strong>Computing
strictly-second shortest
paths</strong></a>, Inf.
Process. Lett. 63, No. 4, 177-181 (1997).
<a href="https://zbmath.org/?q=an:1336.68137" rel="nofollow noreferrer">ZBL1336.68137</a>.</p>
</li>
<li><p>[2004] <em>Krasikov, I.;
Noble, S. D.</em>, <a href="https://doi.org/10.1016/j.ipl.2004.06.020" rel="nofollow noreferrer"><strong>Finding next-to-shortest paths in a
graph</strong></a>, Inf. Process.
Lett. 92, No. 3, 117-119 (2004).
<a href="https://zbmath.org/?q=an:1173.68609" rel="nofollow noreferrer">ZBL1173.68609</a>.</p>
</li>
<li><p>[2006] <em>Li, Shisheng; Sun, Guangzhong; Chen, Guoliang</em>,
<a href="https://doi.org/10.1016/j.ipl.2006.04.013" rel="nofollow noreferrer"><strong>Improved algorithm for finding next-to-shortest
paths</strong></a>, Inf. Process.
Lett. 99, No. 5, 192-194 (2006).
<a href="https://zbmath.org/?q=an:1185.68489" rel="nofollow noreferrer">ZBL1185.68489</a>.</p>
</li>
<li><p>[2011] <em>Kao, Kuo-Hua; Chang, Jou-Ming; Wang, Yue-Li;
Juan, Justie Su-Tzu</em>, <a href="https://doi.org/10.1007/s00453-010-9402-4" rel="nofollow noreferrer"><strong>A quadratic algorithm for finding
next-to-shortest paths in
graphs</strong></a>, Algorithmica
61, No. 2, 402-418 (2011).
<a href="https://zbmath.org/?q=an:1250.05108" rel="nofollow noreferrer">ZBL1250.05108</a>.</p>
</li>
<li><p>[2012a] <em>Cong Zhang; Hiroshi Nagamochi</em>, <a href="https://dl.acm.org/doi/abs/10.5555/2523693.2523695" rel="nofollow noreferrer"><strong>The
next-to-shortest path in undirected graphs with nonnegative
weights</strong></a>. In
Proceedings of the Eighteenth Computing: The Australasian Theory
Symposium - Volume 128 (CATS '12). Australian Computer Society, Inc.,
AUS, 13–20.</p>
</li>
<li><p>[2012b] <em>B.Y. Wu, J.-L. Guo, and Y.-L. Wang</em>, <a href="https://doi.org/10.48550/arXiv.1203.5235" rel="nofollow noreferrer"><strong>A linear time
algorithm for the next-to-shortest path problem on undirected graphs
with nonnegative edge
lengths</strong></a>, 2012,
arXiv:1203.5235 [cs.DS].</p>
</li>
<li><p>[2015] <em>Wu, Bang Ye;
Wang, Hung-Lung</em>, <a href="https://doi.org/10.1002/net.21598" rel="nofollow noreferrer"><strong>The next-to-shortest path problem on directed
graphs with positive edge
weights</strong></a>, Networks 65, No. 3,
205-211 (2015). <a href="https://zbmath.org/?q=an:1386.05082" rel="nofollow noreferrer">ZBL1386.05082</a>,
(pdf
<a href="http://cedric.cnam.fr/%7Ebentzc/INITREC/Files/CP11.pdf" rel="nofollow noreferrer">here</a>).</p>
</li>
<li><p>[1998] <em>Eppstein, David</em>, <a href="https://doi.org/10.1137/S0097539795290477" rel="nofollow noreferrer"><strong>Finding
the k shortest paths</strong></a>,
SIAM J. Comput. 28, No. 2, 652-673 (1998).
<a href="https://zbmath.org/?q=an:0912.05057" rel="nofollow noreferrer">ZBL0912.05057</a>.</p>
</li>
</ul>

CC BY-SA 4.0
2020-06-05T03:51:00.297Z
We call those unweighted graphs
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2020-06-08T12:09:46.177Z
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.
NYD
CC BY-SA 4.0
2020-06-08T12:56:35.373Z
And how do you proceed, if all resulting paths have the same weight $w(p_1)$ as the original shortest path $p_1$?
Gamow
CC BY-SA 4.0
2020-06-08T12:57:51.290Z
Got it. Thank you!
NYD
CC BY-SA 4.0
2020-11-10T17:24:28.410Z
This paper solves the unweighted problem in $O(n^2)$: [A Quadratic Algorithm for Finding Next-to-Shortest
Paths in Graphs](https://link.springer.com/article/10.1007/s00453-010-9402-4)
isaacg
CC BY-SA 4.0
2021-03-09T00:25:43.093Z
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."
Andras Farago
CC BY-SA 4.0
2024-02-19T17:34:22.997Z
The confusion here is that the $O(n^2)$-time algorithm is for *undirected* graphs  (with positive edge weights).  Later work gives poly-time algorithm for undirected graphs with non-negative edges weights.  But as far as I can tell (as of 2023) the variant on *directed* graphs with *positive* edge weights (asking for a *simple* path, not a walk), is open.  [I attempted to address all this in an edit of the post.]
Neal Young
CC BY-SA 4.0
2024-03-23T14:22:06.150Z
By the way, as of 2023, the following similar problem is still open: given an unweighted directed graph G and vertices s and t, decide if there is a a simple path from s to t which is strictly longer than the shortest path. (It needn't be the next-to-shortest, just longer than the shortest.) This is explicitly stated here: https://arxiv.org/abs/2307.01781 "it remains open whether k-Longest Detour is in P even for the special case of k = 1"
Antoine Amarilli 'a3nm'
<np-hardness><shortest-path>
Recent progress on the next-to-shortest-path problem for directed graphs?
user514014
# Recent progress on the next-to-shortest-path problem for directed graphs?

(Asked by: username_0 on 2020-06-05)

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

---

* [1997] *Lalgudi, Kumar N.; Papaefthymiou, Marios C.*, [**Computing
  strictly-second shortest
  paths**](https://doi.org/10.1016/S0020-0190(97)00122-1), Inf.
  Process. Lett. 63, No. 4, 177-181 (1997).
  [ZBL1336.68137](https://zbmath.org/?q=an:1336.68137).
* [2004] *Krasikov, I.;
  Noble, S. D.*, [**Finding next-to-shortest paths in a
  graph**](https://doi.org/10.1016/j.ipl.2004.06.020), Inf. Process.
  Lett. 92, No. 3, 117-119 (2004).
  [ZBL1173.68609](https://zbmath.org/?q=an:1173.68609).
* [2006] *Li, Shisheng; Sun, Guangzhong; Chen, Guoliang*,
  [**Improved algorithm for finding next-to-shortest
  paths**](https://doi.org/10.1016/j.ipl.2006.04.013), Inf. Process.
  Lett. 99, No. 5, 192-194 (2006).
  [ZBL1185.68489](https://zbmath.org/?q=an:1185.68489).
* [2011] *Kao, Kuo-Hua; Chang, Jou-Ming; Wang, Yue-Li;
  Juan, Justie Su-Tzu*, [**A quadratic algorithm for finding
  next-to-shortest paths in
  graphs**](https://doi.org/10.1007/s00453-010-9402-4), Algorithmica
  61, No. 2, 402-418 (2011).
  [ZBL1250.05108](https://zbmath.org/?q=an:1250.05108).
* [2012a] *Cong Zhang; Hiroshi Nagamochi*, [**The
  next-to-shortest path in undirected graphs with nonnegative
  weights**](https://dl.acm.org/doi/abs/10.5555/2523693.2523695). In
  Proceedings of the Eighteenth Computing: The Australasian Theory
  Symposium - Volume 128 (CATS '12). Australian Computer Society, Inc.,
  AUS, 13–20.
* [2012b] *B.Y. Wu, J.-L. Guo, and Y.-L. Wang*, [**A linear time
  algorithm for the next-to-shortest path problem on undirected graphs
  with nonnegative edge
  lengths**](https://doi.org/10.48550/arXiv.1203.5235), 2012,
  arXiv:1203.5235 [cs.DS].
* [2015] *Wu, Bang Ye;
  Wang, Hung-Lung*, [**The next-to-shortest path problem on directed
  graphs with positive edge
  weights**](https://doi.org/10.1002/net.21598), Networks 65, No. 3,
  205-211 (2015). [ZBL1386.05082](https://zbmath.org/?q=an:1386.05082),
  (pdf
  [here](http://cedric.cnam.fr/%7Ebentzc/INITREC/Files/CP11.pdf)).
* [1998] *Eppstein, David*, [**Finding
  the k shortest paths**](https://doi.org/10.1137/S0097539795290477),
  SIAM J. Comput. 28, No. 2, 652-673 (1998).
  [ZBL0912.05057](https://zbmath.org/?q=an:0912.05057).

**Tags:** np-hardness, shortest-path

> **Comments:**
> **username_1**: We call those unweighted graphs  
> **username_2**: 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.  
> **username_3**: And how do you proceed, if all resulting paths have the same weight $w(p_1)$ as the original shortest path $p_1$?  
> **username_2**: Got it. Thank you!  
> **username_4**: This paper solves the unweighted problem in $O(n^2)$: [A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs](https://link.springer.com/article/10.1007/s00453-010-9402-4)  
> **username_5**: In the Conclusion section of paper referred in the comment of  username_4 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."  
> **username_6**: The confusion here is that the $O(n^2)$-time algorithm is for *undirected* graphs  (with positive edge weights).  Later work gives poly-time algorithm for undirected graphs with non-negative edges weights.  But as far as I can tell (as of 2023) the variant on *directed* graphs with *positive* edge weights (asking for a *simple* path, not a walk), is open.  [I attempted to address all this in an edit of the post.]  
> **username_7**: By the way, as of 2023, the following similar problem is still open: given an unweighted directed graph G and vertices s and t, decide if there is a a simple path from s to t which is strictly longer than the shortest path. (It needn't be the next-to-shortest, just longer than the shortest.) This is explicitly stated here: https://arxiv.org/abs/2307.01781 "it remains open whether k-Longest Detour is in P even for the special case of k = 1"  

---

## 0 answers

