Demostrando que el diagnóstico gráfico dirigido es NP-duro

Question

Tengo una tarea que estoy dale que dale mi cabeza contra por algún tiempo, y te agradecería alguna pista. Se trata de elegir un problema conocido, la NP-completitud de los cuales se ha demostrado, y la construcción de una reducción de ese problema a la siguiente problema que llamaré DGD (dirigida diagnóstico gráfico).

Problema

Una instancia de DGD $ (V, E, k) $ consisten de vértices $ V = I \ desbordadas {.} {\ Taza} O \ desbordadas {.} {\ Taza} B $, dirigida bordes $ E $ y un entero positivo k $ $. Hay tres tipos de vértices: vértices con bordes entrantes sólo $ I $, vértices con bordes salientes sólo $ O $ y vértices con ambos bordes entrantes y salientes $ B $. Además Deje $ D = S \ times I $.

Ahora, el problema es si podemos cubrir todos los nodos con a lo sumo $ k elementos de $ $ D $, es decir.

$ \ qquad \ displaystyle \ existe \, S \ subseteq D, | S |. \ Leq k \ \ forall \, v \ in V \ \ existe \, (v 1, v_2) \ en S. \ v 1 \ a ^ * v \ a ^ * v_2 $

donde $ a \ a ^ * b $ medios que hay un camino dirigido desde $ a $ y $ b $.

---

Creo que el problema Dominando Set es la que debería ser la reducción de, porque esto también está preocupado por que cubre un subconjunto de nodos con otro subconjunto. He intentado crear una instancia de DGD creando en primer lugar dos nodos para cada elemento del conjunto dominante, la copia de todos los bordes, y luego poner los $ k $ de la instancia DGD igual a la de la instancia DS.

Supongamos que un simple DS-instancia con nodos $ 1 $, $ 2 $ y $ $ 3 y los bordes $ (1,2) $ y $ (1,3) $. Este es un sí instancia con $ k = 1 $; el conjunto que domina en este caso consiste en único nodo $ 1 $. La reducción con el método descrito, esto llevaría a una instancia de DGD con dos caminos $ (1 \ a 2 \ a 1 ') $ y $ (1 \ a 3 \ a 1') $; para cubrir todos los nodos, sólo un par de $ (1, 1' ) $ sería suficiente. Esto habría funcionado a la perfección, si no fuera por el hecho de que el conjunto dominante de la DS-instancia no puede, por supuesto, se determinará en tiempo polinómico, que es un requisito aquí.

He encontrado que hay muchas maneras de buen aspecto para transformar los bordes y vértices cuando se reducen, pero mi problema es de alguna manera la expresión del DGD $ $ k en términos de DS de $ k $. Dominando Conjunto parecía un problema de ajuste para reducir partir, pero debido a esto creo que tal vez debería tratar de reducir a un problema que no tiene tal k $ $?

Answer 1

Reducir de NP-completo SET-COVER lugar.

Let $ S_1, \ dots, S_m \ subseteq \ {1, \ dots, n \} $ con $ k \ in \ mathbb {N} $ una instancia de la cubierta conjunto. Definir una instancia $ (V, E, K ') $ DGD de la siguiente manera:

• $ V = \ {s_1, \ dots, s_m, O_1, \ dots, o_m, e_1, \ dots, e_n, o \} $
• $ E = \ {(S_I, o_i) \ mediados i = 1, \ dots, n \} \ taza \ {(S_I, e_j) \ mediados j \ en S_i \} \ taza \ {(e_j, o ) \ mediados j = 1, \ dots, n \} $
• $ k'= m + k $

Es fácil ver que la instancia DGD construida tiene una respuesta positiva si y sólo si el conjunto de tapa ejemplo dado tiene una respuesta positiva. En particular, todos los pares $ m $ $ (S_i, o_i) $ tienen que ser elegidos sin importar lo que con el fin de cubrir todas o_i $ $; luego $ k $ de los $ m $ pares $ (S_I, o) $ tiene que cubrir todo el $ e_j $, y los primeros componentes de los elegidos son la solución de la instancia SET de la cubierta. Si no hay tal opción es posible la instancia SET-COVER no tiene solución también.

A medida que la construcción es posible en tiempo polinómico, esto demuestra SET-COVER $ \ $ leq_p DGD.

---

Como ejemplo, considere el ejemplo de instancia cobertura dada en Wikipedia , es decir, $ \ {1,2,3,4,5 \} $ y conjuntos $ S = \ {\ {1,2,3 \}, \ {2,4 \}, \ {3,4 \}, \ {4, 5 \} \} $. Esto se traduce en el siguiente gráfico:

^{[ fuente ]}