Jak trudno jest zdecydować o istnieniu idealnego dopasowania czerwono-niebieskiego?

Idealnym rozwiązaniem dwukolorowego dopasowania jest decyzja, czy wykres ma koloryt w dwóch kolorach, tak aby każdy węzeł miał dokładnie jednego sąsiada tego samego koloru co on sam. Schaefer udowodnił, że problem jest NP-zupełny . Pozostaje NP-kompletny nawet dla płaskich wykresów sześciennych.

Interesuje mnie wariant, w którym chcemy zdecydować, czy wykres wejściowy ma zabarwienie dwoma kolorami, tak więc każdy węzeł ma dokładnie jednego sąsiada zabarwionego inaczej. Nazywam to czerwono-niebieskim idealnym dopasowaniem. Nie wiem, czy to znany problem.

Jak trudno jest zdecydować o istnieniu idealnego dopasowania czerwono-niebieskiego?

Jak zauważył Michaił, problem nazywał się literaturą Perfect Matching Cut. Wykazano, że jest on NP-zupełny w następującym artykule (patrz Twierdzenie 1 na stronie 5), ze zmniejszeniem w stosunku do monotonicznego 1-w-3-SAT:

Pinar Heggernes, Jan Arne Telle. Podział wykresów na uogólnione zestawy dominujące.