Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance.

Given a distance $D$, and a graph $G(V,A)$, where $V$ is a set of nodes, $A$ is a set of directed links (or arcs). Each link has two additive metrics, namely, a cost (binary, $0$ or $1$) and a distance (positive integer). For a source-destination pair $(s,t)$, find a set of two paths P1 and P2, where $P_1$ and $P_2$ are arc-disjoint and path distance $L(P_1)\le D$, $L(P_2)\le D$, such that the total cost is minimized. Note that the distance and the cost of a path is the sum of the length and the cost of the links it traverses, respectively.

I knew that when the cost of each arc is integer or real, it is an NP-Complete problem, see GCSDP($k$). I do not know whether it is still NP-complete when the cost of each arc is limited to $\{0,1\}$. Anyway, I want to know if there is a polynomial solution for it.


Your Answer

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

Browse other questions tagged or ask your own question.