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

  • 0
    Migrate to [cs.SE](http://cs.stackexchange.com)?2013-11-17
  • 0
    I think that this problem was found to be NP hard.. You can do it if you want..2013-11-19

1 Answers 1