Probar encontrar rutas de disjoint K de N Dadas rutas en un gráfico dirigido es NP-Completa

Question

Problema: Dados n rutas en un gráfico directo G (v, e) y un entero k, averigüe las rutas K entre ellos de manera que no pasen dos a través de un nodo común.

Demuestra que el problema dado está en NP-Completa.

pude demostrar que el problema está en NP.Sugerencia es que debemos llegar a una reducción de tiempo polinomial del problema establecido independiente a este problema, demuestre que está en NP-HARD.

Answer 1

Membresía de su problema en $ \ mathsf {np} $ es trivial. Para demostrar que también es $ \ mathsf {np} $ -hard Considere una instancia de (la versión de decisión de) Set independiente que consiste en un gráfico $ g= (v, e) $ con $ |== n $ y de un entero $ k $ .

Construir el gráfico $ h= (v ', e') $ donde $ V '= V \ CUP \ {x_ {u, v} \,: \, (u, v) \ in e \} $ y $ e '= v' \ veces v '$ < / span>.

para cada $ u \ in v $ Let $ v_1, v_2, \ dots, v_h $ Sean los vecinos de $ u $ en $ g $ y define la ruta $ p_u=langle u, x_ {u, v_1}, x_ {u, v_2}, \ dots, x_ {u, v_h} \ rangle $ en $ H $ . Deje $ \ mathcal {p}={p_u \,: \, u \ in v \} $ .

Hay un conjunto independiente de tamaño a la mayoría $ k $ en $ g $ , si y Solo si hay un subconjunto $ \ mathcal {p} '$ con $ | \ mathcal {p}' | \ le k $ de tal que las rutas en $ \ mathcal {p} '$ son un vértice de parejas-disjoint.

Más precisamente, si $ s $ es un conjunto independiente de $ g $ , luego $ \ {p_u \,: \, u \ in s \ \ \ in s \} $ es una colección de caminos de vértice en pares en $ h $ y, si $ \ mathcal {p} '$ es una colección de rutas de vertex-disjoint en $ H $ , luego $ \ {u \,: \, p_u \ in \ mathcal {p} '\ \ \ \ \ \ \ \ \ \ \ sport> es un conjunto independiente de < Span Class="Math-contenedor"> $ G $ .