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$

1 Answer 1

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$
5
  • $\begingroup$ I'd be happy to get feedback, is this reduction correct? $\endgroup$ Aug 27, 2014 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, 2014 at 18:53
  • $\begingroup$ @D.W., there was a mistake. It is now fixed. I will be greatful for your opinion. $\endgroup$ Aug 27, 2014 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, 2014 at 21:04
  • $\begingroup$ Thanks @PålGD, I don't understand the variation of PART you have just specified though.. $\endgroup$ Sep 26, 2014 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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