Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths connecting $s$ and $t$, each of which of weight at most $M$?
Call this problem DPBP (for disjoint pair of bounded paths).
Finding a pair of edge disjoint paths with bounded sum of weights is in $POLY$ [Suurballe's algorithm] http://en.wikipedia.org/wiki/Suurballe%27s_algorithm)).
Is DPBP NP-complete?
DPBP is NP-complete.
I give a reduction from the partition problem. Define $\text{PART}=\left\{ {x_1,x_2,\ldots,x_n\in \mathbb{N}|\exists I:\sum_{i\in I}x_i=\sum_{i\not\in I}x_i} \right \}$.
Given an instance $\left \{ {x_1,\ldots ,x_n} \right \}$ of PART, we build a graph in the following way. For each $i\in \left \{{1,\ldots,n} \right \}$, we have a diamond like component. These components are connected in a row, starting from $s$ and ending at $t$:
The weight of the upper left edge in the $i\text{'th}$ component is $x_i$ and all other edges have weights $0$. The constant bounding the paths weight is $M=\frac{1}{2}\sum_{i=1}^n{x_i}$.
A path in this graph between $s$ and $t$ travels through all components. In order for two edge disjoint paths to fit in, each path should travel threw all components, taking either the upper or lower part of each.
Given a partition $I={i_1,\ldots ,i_k}\subset \left\{ {1,\ldots,n} \right\}$, let the first path go threw the upper parts of the components with indexes in $I$, and threw the lower parts of the other components. Since traveling threw the upper part of the $i$'th component costs $x_i$, the weight of this path is exactly $\sum_{i\in I}x_i$. In case the given partition is proper, this sum is exactly $\frac{1}{2}\sum_{i=1}^n x_i = M$.
The second path will be the complement path, i.e., it will go threw the lower part of each component with an index in $I$, and threw the upper part of each component with an index not in $I$. Therefore, its weight will be $\sum_{i\not \in I}x_i=\sum_{i=1}^n x_i - \sum_{i\in I}x_i=M$ as well.
Thus, the two paths are edge disjoint and bounded by $M$ as required.
Now, assume that we are given a pair of edge disjoint paths between $s$ and $t$, so that the weights of each is at most $M$. By the construction, the weight of each is exactly $M$. Let $I=\left\{ {i_1,\ldots,i_k} \right\}$ be the components with an upper part traveled by the first path. Obviously, $I$ partitions the $x_i$'s properly.
