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?
cc.complexity-theory
np-hardness
Mohammad Al-Turkistany
źródło
źródło
Odpowiedzi:
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.
źródło