[Solved]: Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Problem Detail: 

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 has weight at most $M$? In other words, we are given an upper bound on the path weights, and we want to know whether there exists two paths from $s$ to $t$ that don't have any edge in common.

Call this problem DPBP (for disjoint pair of bounded paths).

Is DPBP NP-complete?

A variant of this problem can be solved in polynomial time. In particular, Suurballe's algorithm can be used to find a pair of edge-disjoint paths where the sum of their weights is minimal; thus, it can be used to decide whether there exists a pair of edge-disjoint paths such that their weights sum to at most $M$. But what about when we require each path to have weight at most $M$, instead of requiring that their two weights sum to at most $M$?

Asked By : Yoav bar sinai

Answered By : Yoav bar sinai

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29438

3.2K people like this

 Download Related Notes/Documents