Mostrar que la eliminación mínima de vértices en un gráfico bipartito es NP-completo

Considere el siguiente problema cuya instancia de entrada es un gráfico simple y un entero natural . $G$ $k$

¿Existe un conjunto tal que sea bipartito y ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Me gustaría mostrar que este problema es -completo reduciendo 3-SAT, CLIQUE, -DOMINATING SET o -VERTEX COVER a él. $\rm{NP}$ $k$ $k$ $k$

Creo que puedo reducir el problema de 3 COLORES, por lo que solo necesitaría ver cómo reducir uno de los problemas mencionados. Pero como eso sería bastante complicado, me pregunto si alguien ve una reducción elegante a los problemas antes mencionados.

Además, ¿hay un nombre para este problema de decisión?

complexity-theory np-complete reductions Jernej
fuente

Transversal de ciclo impar .

Pål GD

Esto parece similar al conjunto de vértices de retroalimentación . Es decir, desea encontrar un subconjunto mínimo de vértices para eliminar de modo que el gráfico resultante sea acíclico. Un gráfico acíclico es, por definición, un árbol (o bosque) que es bipartito.

Nicholas Mancuso

@NicholasMancuso No es tan similar. Es realmente como digo más arriba, el problema transversal del ciclo impar. O como señala Vor, Yannakakis lo llamó eliminación del nodo bipartito (o vértice) en los años 70 y 80.

Pål GD

@ PålGD, estoy de acuerdo. Sentí que la reducción más fácil sería de FVS. Sin embargo, eso se hace innecesario por su definición como Odd Cycle Transversal.

Nicholas Mancuso

@Jernej: dices "... me gustaría mostrar que este problema está en NP reduciéndolo a 3-SAT, la CLIQUE k, ...". ¿Quiere decir "Me gustaría mostrar que este problema es NP-hard usando una reducción de 3-SAT, k-CLIQUE, ..."? (el problema está claramente en NP porque la prueba si un gráfico es bipartito se puede hacer en tiempo lineal)

Vor

Respuestas:

Su problema es un caso especial de una clase más amplia de problemas llamados problemas de eliminación de nodos :

JM Lewis y M. Yannakakis, "El problema de eliminación de nodos para propiedades hereditarias es NP-completo"

... Este artículo trata sobre la clase de problemas de gráficos definidos de la siguiente manera:
para una propiedad de gráfico fija , encuentre el número mínimo de nodos (o vértices) que deben eliminarse de un gráfico dado para que el resultado satisfaga . Llamamos a esto el problema de eliminación de nodos para . Nuestros resultados muestran que si es una propiedad no trivial que es hereditaria en un subgrafo inducido, entonces el problema de eliminación de nodos para es NP-duro. Además, si agregamos la condición de que la prueba para $\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ se puede realizar en tiempo polinómico, entonces nuestros resultados implican que el problema de eliminación de nodos para es NP completo. ... $\Pi$

Su problema es el problema de eliminación de nodos para bipartidismo , pero (como lo señaló Pal), hoy se conoce como el problema de desplazamiento del ciclo impar (OCT).

EDITAR

En lo que respecta a una reducción directa, pensé en esta de 3SAT.

Dada una instancia de 3SAT con variables y cláusulas, construya el siguiente gráfico: agregue dos nodos para cada variable y un borde entre ellos. Para simular una asignación de verdad, agregue nodos para cada variable y conéctelos a y ; de esta manera, para hacer que un gráfico bipartito elimine como máximo nodos, se debe eliminar al menos uno entre y . Finalmente para cada clausula $n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ agrega 4 nodos y crea un ciclo impar que conecta las variables en . $C_j$ $C_j$

El gráfico resultante se puede hacer bipartito eliminando en la mayoría de los nodos si y solo si la fórmula 3SAT original es satisfactoria. $G$ $n$

ingrese la descripción de la imagen aquí

Vor
fuente

Esta no es realmente la respuesta que pide la pregunta. OP quiere reducir explícitamente usando el problema dado. Además, el problema se conoce hoy como Odd Cycle Transversal.

Pål GD

@ PålGD: tienes razón.

Vor

Sí, pero no puedo ver inmediatamente una reducción de la lista de problemas de OP, aunque ... Solo sé del que mencionas, por Yannakakis.

Pål GD

@ PålGD: pensaré en una reducción diferente, pero para ser honesto, no estoy seguro de qué es exactamente lo que quiere el OP (vea mi comentario más arriba).

Vor

@Vor Lo que quiero es ver una reducción simple a uno de uno de los problemas mencionados. Conozco este artículo, pero estoy buscando la reducción más directa.

Jernej