5
$\begingroup$

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.

$\endgroup$

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.