O problema de correspondência perfeita de duas cores é decidir se um gráfico tem cores com duas cores, de modo que cada nó tenha exatamente um vizinho da mesma cor que ele. O problema foi provado como NP-completo por Schaefer . Permanece NP-completo mesmo para gráficos cúbicos planares.
Estou interessado em uma variante na qual queremos decidir se o gráfico de entrada tem cores com duas cores, de modo que cada nó tem exatamente um vizinho colorido diferentemente dele. Eu chamo isso de problema de correspondência perfeita vermelho-azul. Não sei se isso é um problema conhecido.
Quão difícil é decidir a existência de uma combinação perfeita de vermelho e azul?
cc.complexity-theory
np-hardness
Mohammad Al-Turkistany
fonte
fonte
Respostas:
Como Mikhail observou, o problema foi chamado de Perfect Matching Cut nas literaturas. Foi provado ser NP-completo no documento a seguir (consulte o Teorema 1 na página 5), com uma redução do monótono 1-em-3-SAT:
Pinar Heggernes, Jan Arne Telle. Particionando gráficos em conjuntos dominantes generalizados.
fonte