Encontrar a un par de borde caminos separados en un gráfico, que limita el peso de cada uno de ellos

Question

Dado un grafo no dirigido a $G=(V,E)$, dos vértices $s,t\in V$, una función peso $f:E \to \mathbb{N}$, y una constante$M\in \mathbb{N}$, ¿existe un par de borde discontinuo caminos que conectan $s$$t$, cada uno de los cuales de peso en la mayoría de las $M$?

Llame a este problema DPBP (para discontinuo par de limitada caminos).

Encontrar un par de borde discontinuo caminos con delimitada suma de pesos es en $POLY$ [Suurballe del algoritmo] http://en.wikipedia.org/wiki/Suurballe%27s_algorithm)).

Es DPBP NP-completo?

Answer 1

DPBP es NP-completo.

Doy una reducción de la partición problema. Definir $\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 \}$.

Dada una instancia $\left \{ {x_1,\ldots ,x_n} \right \}$ de la PARTE, podemos construir una gráfica de la siguiente manera. Para cada una de las $i\in \left \{{1,\ldots,n} \right \}$, tenemos un diamante como componente. Estos componentes están conectados en una fila, a partir de $s$ y terminando en $t$:

El peso de la parte superior del borde izquierdo de la $i\text{'th}$ componente es $x_i$ y todos los otros bordes de pesos $0$. La constante de la delimitación de la rutas de peso es $M=\frac{1}{2}\sum_{i=1}^n{x_i}$.

Un camino en este gráfico entre $s$ $t$ viaja a través de todos los componentes. En orden para dos borde discontinuo caminos para caber en cada ruta debe viajar tiró todos los componentes, tomando la parte superior o la parte inferior de cada uno.

Dada una partición $I={i_1,\ldots ,i_k}\subset \left\{ {1,\ldots,n} \right\}$, vamos a la primera ruta de ir tiró de la parte superior de los componentes con los índices en $I$, y tiró de las partes inferiores de los otros componentes. Desde viajar tiró de la parte superior de la $i$'th componente de los costos de $x_i$, el peso de esta ruta es exactamente $\sum_{i\in I}x_i$. En caso de que la partición indicada es la correcta, esta suma es exactamente $\frac{1}{2}\sum_{i=1}^n x_i = M$.

La segunda ruta será la de complementar la ruta, es decir, se va a ir tiró de la parte inferior de cada componente con un índice en $I$, y tiró de la parte superior de cada componente con un índice no en $I$. Por lo tanto, su peso será$\sum_{i\not \in I}x_i=\sum_{i=1}^n x_i - \sum_{i\in I}x_i=M$.

Por lo tanto, los dos caminos son el borde discontinuo y delimitado por la $M$ como se requiere.

Ahora, suponga que nos dan un par de borde discontinuo caminos entre el$s$$t$, por lo que el peso de cada uno es en la mayoría de las $M$. Por la construcción, el peso de cada uno es exactamente $M$. Deje $I=\left\{ {i_1,\ldots,i_k} \right\}$ ser los componentes con una parte superior recorrida por el primer camino. Obviamente, $I$ particiones de la $x_i$'s correctamente.