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

11

Tengo una tarea para la cual me he estado golpeando la cabeza durante algún tiempo, y agradecería cualquier pista. Se trata de elegir un problema conocido, cuya integridad NP está probada, y construir una reducción de ese problema al siguiente problema que llamaré DGD (diagnóstico de gráfico dirigido).

Problema

Una instancia de DGD consiste en vértices , bordes dirigidos y un entero positivo . Hay tres tipos de vértices: vértices con bordes entrantes sólo , vértices con bordes salientes solamente y vértices con tanto entrantes como salientes bordes . Dejar que, además, .V = I . O . B E k I O B D = O × I(V,E,k)V=I.O.BEkIOBD=O×I

Ahora, el problema es si podemos cubrir todos los nodos con a lo sumo elementos de , es decirDkD

SD,|S|k. vV. (v1,v2)S. v1vv2

donde significa que hay una ruta dirigida de a .a babab


Creo que el problema del conjunto dominante es el que debería reducir, porque esto también está preocupado por cubrir un subconjunto de nodos con otro subconjunto. Intenté crear una instancia DGD creando primero dos nodos para cada elemento del conjunto dominante, copiando todos los bordes y luego estableciendo la de la instancia DGD igual a la de la instancia DS.k

Supongamos una instancia DS simple con nodos , y y bordes y . Esta es una instancia de sí con ; el conjunto dominante en este caso consiste solo en el nodo . Reduciendo con el método que se acaba de describir, esto conduciría a una instancia DGD con dos rutas y ; para cubrir todos los nodos, solo un par sería suficiente. Esto hubiera funcionado perfectamente, de no ser por el hecho de que el conjunto dominante de la instancia DS no puede, por supuesto, determinarse en tiempo polinómico, lo cual es un requisito aquí.2 3 ( 1 , 2 ) ( 1 , 3 ) k = 1 1 ( 1 2 1 ) ( 1 3 1 ) ( 1 , 1 )123(1,2)(1,3)k=11(121)(131)(1,1)

He descubierto que hay muchas formas atractivas de transformar los bordes y vértices al reducir, pero mi problema es expresar de alguna manera la de DGD en términos de de DS . Dominar a Set parecía un problema apropiado para reducir, pero debido a esto, creo que tal vez debería tratar de reducir un problema que no tiene tal .k kkkk

usuario8879
fuente
¡Bienvenidos! Traté de aclarar el enunciado del problema; ¿Es así como lo dijiste en serio? Por cierto, es posible que desee elegir un nombre de usuario más reconocible que "user8879". :)
Raphael
Sí, gracias, esta es una versión más compacta.
user8879

Respuestas:

9

Reduzca de NP-complete SET-COVER en su lugar.

Deje con una instancia de la cubierta del conjunto. Defina una instancia de DGD como esta:k N ( V , E , k S1,,Sm{1,,n}kN(V,E,k)

  • V={s1,,sm,o1,,om,e1,,en,o}
  • E={(si,oi)i=1,,n}{(si,ej)jSi}{(ej,o)j=1,,n}
  • k=m+k

Es fácil ver que la instancia DGD construida tiene una respuesta positiva si y solo si la instancia de cobertura de conjunto dada tiene una respuesta positiva. En particular, todos los pares de tienen que elegirse sin importar para cubrir todos los ; entonces de los pares tienen que cubrir todos los , y los primeros componentes de los elegidos son la solución de la instancia SET-COVER. Si tal opción no es posible, la instancia SET-COVER tampoco tiene solución.m(si,oi)oikm(si,o)ej

Como la construcción es posible en tiempo polinómico, esto demuestra SET-COVER DGD.p


Como ejemplo, considere la instancia de portada de conjunto de ejemplos dada en Wikipedia , a saber, y establece . Esto se traduce en el siguiente gráfico:{1,2,3,4,5}S={{1,2,3},{2,4},{3,4},{4,5}}

ejemplo
[ fuente ]

Rafael
fuente
1
Esto es casi correcto, ya que I y B están completamente cubiertos, pero O no. La instancia set-cover es una instancia yes para k = 2, pero en la instancia DGD k = 2 deja s2 y s3 sin cubrir. Creo que esto probablemente se pueda resolver agregando automáticamente un borde de cada nodo en O a o .
user8879
@ user8879: Oh maldita sea, cierto. La forma en que el problema se plantea ahora, los bordes se lo arregle, porque a fin de cubrir que necesita al menos un par que lo contiene en . s i S(si,o)siS
Rafael
Lo tengo ahora: cree un nodo adicional en B para cada nodo en O , luego vincúlelo a su nodo correspondiente en O y a o . En este ejemplo, obtiene cuatro rutas adicionales (s1 -> s1 '-> o, etc.). Finalmente, después de aumentar k con cuatro, debería estar completo.
user8879
@ user8879: lo arregló ahora. Necesitamos algunos nodos adicionales que prevengan que todos los estén cubiertos, pero seguimos teniendo un tamaño polinómico. (Oh, comentaste mientras estaba arreglando, bien hecho).si
Raphael