3
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

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 Graph

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.

$\endgroup$
  • $\begingroup$ I'd be happy to get feedback, is this reduction correct? $\endgroup$ – Yoav bar sinai Aug 27 '14 at 18:10
  • $\begingroup$ I don't understand why the last sentence in your answer follows. I suggest you elaborate on that in a lot more detail, as that is the key part of the proof. Why do you say that if there is a pair of edge disjoint paths, then there is a partition of the given numbers? $\endgroup$ – D.W. Aug 27 '14 at 18:53
  • $\begingroup$ @D.W., there was a mistake. It is now fixed. I will be greatful for your opinion. $\endgroup$ – Yoav bar sinai Aug 27 '14 at 20:16
  • $\begingroup$ Good proof. I think (I don't have it at hand) that Garey & Johnson specify that Partition remains NP-hard when you are giving $n$ pairs $(x_1,y_1), (x_2, y_2), \dots, (x_n, y_n)$ and you have to pick exactly one of each pair. This means that your edges can have weights $x_i$ and $y_i$. But maybe your proof is just as nice. $\endgroup$ – Pål GD Sep 26 '14 at 21:04
  • $\begingroup$ Thanks @PålGD, I don't understand the variation of PART you have just specified though.. $\endgroup$ – Yoav bar sinai Sep 26 '14 at 21:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.