8
$\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)$?

$\endgroup$
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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\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 at 12:56
  • $\begingroup$ Got it. Thank you! $\endgroup$ – NYD Jun 8 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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