¿El problema del conjunto dominante está restringido a gráficos bipartitos planos de grado máximo 3 NP-completo?

18

¿Alguien sabe acerca de un resultado de completitud NP para el problema DOMINATORIO SET en gráficos, restringido a la clase de gráficos bipartitos planos de grado máximo 3?

Sé que es NP completo para la clase de gráficos planos de grado máximo 3 (ver el libro de Garey y Johnson), así como para gráficos bipartitos de grado máximo 3 (ver M. Chlebík y J. Chlebíková, "Dureza aproximada de dominando problemas de conjunto en gráficos de grados acotados "), pero no se pudo encontrar la combinación de ambos en la literatura.

Florent Foucaud
fuente
3
La próxima vez, enlace a la publicación original si realiza una publicación cruzada. mathoverflow.net/questions/43720/… . Consulte también nuestra entrada de preguntas frecuentes sobre la publicación cruzada .
Tsuyoshi Ito
3
(1) ¿Se sabe algo si aumenta 3 a alguna otra constante? (2) ¿Se sabe algo sobre el caso especial en el que "grado máximo 3" se restringe aún más a "3-regular"? (¿Se sabe que está en P? ¿Se sabe que es equivalente al caso de grado máximo 3?) (3) Por curiosidad, ¿hay alguna aplicación de esto, o le interesa únicamente por sí mismo? (Por si acaso, no estoy diciendo que un problema sin una aplicación sea malo. Lo pregunto porque si tiene alguna aplicación, puede hacer que la pregunta sea más interesante.)
Tsuyoshi Ito
(1) No que yo sepa (2) No. Pero también espero que sea difícil (3) La única aplicación para mí sería obtener la dureza NP de algunos otros problemas en esta misma clase, realmente restringida. gráficos
Florent Foucaud

Respuestas:

24

¿Qué sucede si simplemente hace lo siguiente? Dado un gráfico , construya otro gráfico G ' = ( V U , E ) subdividiendo cada borde de G en 4 partes; aquí U es el conjunto de nuevos nodos que presentamos, y | U | = 3 | E | .G=(V,E)G=(VU,E)GU|U|=3|E|

El gráfico es bipartito. Además, si G es plano y tiene máx. grado 3, entonces G ' también es plano y tiene máx. grado 3.GGG

Sea un conjunto dominante (mínimo) para G . Considere una arista ( x , y ) E que se subdividió para formar una ruta ( x , a , b , c , y ) en G ' . Ahora claramente al menos uno de a , b , c está en D ' . Además, si tenemos más de uno de a , b , c en D ' , podemos modificarDG(x,y)E(x,a,b,c,y)Ga,b,cDa,b,cD para que siga siendo un conjunto dominante válido y su tamaño no aumente. Por ejemplo, si tenemos una D y c D , igualmente podemos eliminar c de D y agregar y a D . De ahí wlog tenemos | D U | = | E | .DaDcDcDyD|DU|=|E|

Entonces considere . Suponga que x V y x D . Entonces debemos tener un nodo a D tal que ( x , a ) E . Por lo tanto, hay una arista ( x , y ) E tal que tenemos una ruta ( x , a , b , c , y ) en G D=DVxVxDaD(x,a)E(x,y)E(x,a,b,c,y)G . Como y a a,b,cU , tenemos b , c D , y para dominar c debemos tener y D . Por lo tanto en G nodo y es un vecino de x con y D . Es decir, D es un conjunto dominante de G .aDb,cDcyDGyxyDDG

Por el contrario, considere un (mínimo) que domina conjunto de G . Construya un conjunto dominante D ' para G ' para que | D | = | D | + | E | como sigue: Para un borde ( x , y ) E que fue subdividido para formar una trayectoria ( x , un , b , c , y ) en G ' , se añade una aDGDG|D|=|D|+|E|(x,y)E(x,a,b,c,y)Ga si x D e y D ; agregamos c a D si x D e y D ; y de lo contrario agregamos b a D ' . Ahora se puede comprobar que D ' es un conjunto dominante para G ' : por construcción, todos los nodos en U están dominados. Ahora dejemos x V D . Entonces hay una y V tal queDxDyDcDxDyDbDDGUxVDyV , y por lo tanto a lo largo del camino ( x , a , b , c , y ) tenemos una D , que domina x .(x,y)E(x,a,b,c,y)aDx

En resumen, si tiene un conjunto dominante de tamaño k , entonces G ' tiene un conjunto dominante de tamaño como máximo k + | E | , y si G ' tiene un conjunto dominante de tamaño k + | E | , entonces G tiene un conjunto dominante de tamaño como máximo k .GkGk+|E|Gk+|E|Gk

Editar: se agregó una ilustración. Arriba: el gráfico original ; centro: gráfico G ' con un conjunto dominante "normalizado"; abajo: gráfico G ' con un conjunto dominante arbitrario.GGG

An example

Jukka Suomela
fuente
1
Buena respuesta.
Mohammad Al-Turkistany
Gracias, eso responde muy bien a mi pregunta (incluso sin las imágenes bonitas;)) ¿Alguien sabe de una referencia en la que se estudian otros problemas de gráficos NP-hard (clásicos) (por ejemplo, cubierta de vértice u otros problemas de dominación) en gráficos planos bipartitos de grado acotado? Creo que eso debería ser interesante.
Florent Foucaud
2
Si responde la pregunta, tal vez debería considerar aceptar la respuesta ... :) Con respecto a otros problemas, la cobertura de vértices es fácil en cualquier gráfico bipartito . Pero supongo que los conjuntos dominantes de borde podrían ser un problema natural para estudiar en este entorno.
Jukka Suomela
Ok, gracias por recordarme el teorema de König y marcar la casilla verde;)
Florent Foucaud
Respuesta sólida Jukka!
Gabriel Fair