¿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.
cc.complexity-theory
graph-theory
Florent Foucaud
fuente
fuente
Respuestas:
¿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′=(V∪U,E′) G U |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.G′ G G′
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 modificarD′ G′ (x,y)∈E (x,a,b,c,y) G′ a,b,c D′ a,b,c D′ 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 | .D′ a∈D′ c∈D′ c D′ y D′ |D′∩U|=|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=D′∩V x∈V x∉D′ a∈D′ (x,a)∈E′ (x,y)∈E (x,a,b,c,y) G′ . Como y a ∈a,b,c∈U , 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 .a∈D′ b,c∉D′ c y∈D′ G y x y∈D D G
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 aD G D′ G′ |D′|=|D|+|E| (x,y)∈E (x,a,b,c,y) G′ a 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 queD′ x∉D y∈D c D′ x∈D y∉D b D′ D′ G′ U x∈V∖D′ y∈V , 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) a∈D′ x
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 .G k G′ k+|E| G′ k+|E| G k
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.G G′ G′
fuente