El problema de coincidencia perfecta de dos colores es decidir si un gráfico tiene una coloración con dos colores de manera que cada nodo tenga exactamente un vecino del mismo color que él. Schaefer demostró que el problema era NP completo . Sigue siendo NP-completo incluso para gráficos cúbicos planos.
Estoy interesado en una variante en la que queremos decidir si el gráfico de entrada tiene color con dos colores, por lo que cada nodo tiene exactamente un vecino coloreado de manera diferente de sí mismo. Yo llamo a esto problema de correspondencia perfecta rojo-azul. No sé si este es un problema conocido.
¿Qué tan difícil es decidir la existencia de una combinación perfecta Rojo-Azul?
cc.complexity-theory
np-hardness
Mohammad Al-Turkistany
fuente
fuente
Respuestas:
Como observó Mikhail, el problema se llamó Corte perfecto a juego en la literatura. Se demostró que tenía NP completo en el siguiente artículo (ver Teorema 1 en la página 5), con una reducción de monótono 1 en 3 SAT:
Pinar Heggernes, Jan Arne Telle. Particionar gráficos en conjuntos dominantes generalizados.
fuente