Reducción de la cubierta del vértice para dominar el conjunto

Question

Estoy tratando de reducir el problema de la cubierta de vértices (decisión) al problema del conjunto (decisión) dominante para demostrar que este último es NP-HARD. Después de una investigación en línea, descubrí que muchos artículos utilizan una reducción que transforma la entrada para el problema de la cubierta de vértices en una entrada para el problema del conjunto dominante creando un triángulo para cada borde. aquí es uno de esos artículos (vea la pregunta 7 en el enlace).

La pregunta que me gustaría preguntar es, si bajamos los vértices aislados en la entrada al problema del conjunto dominante, entonces, podríamos encontrar un contraejemplo a la reducción: deje que la entrada al problema de la cubierta de vértice sea un gráfico que contiene $ n $ nodos y parámetros aislados $ k= n $ . Ahora, la entrada al problema del conjunto dominante será claramente un gráfico vacío con el parámetro $ k= n $ . Ahora, hay una cubierta de vértice de tamaño $ n $ . Pero no es un conjunto dominante del gráfico transformado (es decir, la respuesta al problema de la cubierta del vértice es sí, pero la respuesta al problema de la cubierta establecedor dominante es no).

¿Cómo podría arreglar la reducción? ¿Podría alguien por favor aconsejarme?

Answer 1

Si entiendo correctamente, solo tiene un problema cuando el gráfico $ g= (v, e) $ de la instancia de la cubierta de vértices tiene vértices aislados. En este caso, puede transformar $ g $ en un gráfico relacionado $ g '= (v \ cuco \ {x, y \}, E ') $ agregando un nuevo vértice $ x $ y $ y $ tal que $ x $ y $ y $ están conectados entre sí por un borde, y allí es un borde entre $ x $ y mutuamente un vértice en $ v $ . Formalmente: $ e '= e \ cup \ {(x, v) \ mid v \ in v \ cup \ {y \ \ \ \ \ \ {span>.

Si $ g $ admite una cubierta de vértices $ c $ de tamaño a la mayoría de la clase $ K $ , luego $ g '$ admite una cubierta de vértice de tamaño en la mayoría de $ K + 1 $ , a saber, $ c \ copa \ {x \} $ .

Si $ g '$ admite una cubierta de vértices $ c $ de tamaño a lo sumo $ K + 1 $ , luego $ g $ admite una cubierta de vértice de tamaño a la mayoría de $ k $ . Esto se puede ver fácilmente notando que $ C \ setminus \ {x, y \} $ debe cubrir todos los bordes en $ E $ , y ese $ (x, y) \ in e '$ garantiza que al menos uno de $ x $ y $ y $ está en $ c $ , es decir, $ | C \ SETMINUS \ {x, y \} |= | C | - | C \ cap \ {x, y \} | \ le | c | - 1 \ le k $ .

Desde $ g '$ no tiene un vértice aislado, ahora puede transformarlo con seguridad en el gráfico $ H $ < / SPAN> de la instancia de conjunto dominante (usando la reducción conocida). De esta manera, usted muestra que $ g $ tiene una cubierta de vértice de tamaño en la mayoría de $ k $ < Span Class="Math-contenedor"> $ \ iff $ $ H $ tiene un conjunto dominante de tamaño en la mayoría de $ k + 1 $ .