# Find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

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.