Le problème de correspondance parfaite bicolore consiste à décider si un graphique a une coloration à deux couleurs de sorte que chaque nœud a exactement un voisin de la même couleur que lui. Schaefer a démontré que le problème était NP-complet . Il reste NP-complet même pour les graphes cubiques planaires.
Je m'intéresse à une variante où nous voulons décider si le graphe d'entrée a une coloration avec deux couleurs telles que chaque nœud a exactement un voisin coloré différemment de lui-même. J'appelle ce problème de correspondance parfaite rouge-bleu. Je ne sais pas si c'est un problème connu.
Quelle est la difficulté de décider de l'existence d'une correspondance parfaite rouge-bleu?
cc.complexity-theory
np-hardness
Mohammad Al-Turkistany
la source
la source
Réponses:
Comme Mikhail l'a noté, le problème s'appelait Perfect Matching Cut dans les littératures. Il s'est avéré être NP-complet dans l'article suivant (voir Théorème 1 à la page 5), avec une réduction par rapport au monotone 1-in-3-SAT:
Pinar Heggernes, Jan Arne Telle. Partitionnement des graphiques en ensembles dominants généralisés.
la source