Correspondance parfaite dans le graphique bipartite avec des bords mutuellement exclusifs

Question

problème

Je voudrais résoudre correspondance parfaite dans le problème de graphique bipartite où certains bords sont mutuellement exclusifs .

.

exemple

sommets de gauche: A, B, C $

sommets droits: $ x, y, z $

bords: $ (a, x), (a, y), (b, z), (c, y) $

paires exliscive: $ (b, z) $ et $ (c, y) $

Réponse: pas de correspondance parfaite

question

est le problème dans p ou np ?

tentatives de solution

Je sais que correspondance parfaite dans le graphique bipartite Problème est dans p .Mais je ne trouve pas d'algorithmes de temps polynomial pour la version ci-dessus de ce problème.J'ai également essayé de prouver que c'est np , mais sans chance.

Answer 1

c'est $ np $ comme $ SAT $ peut être réduit polynométiquement à ce problème.

Laissez les clauses être les verticaux de la partie gauche et les littéraux constituent la partie droite des sommet.Dessinez un bord $ (x, y) $ iff clause $ x $ contient littéral $ y $ .Enfin, une paire de bords $ (x_1, y_1) $ et $ (x_2, y_2) $ seraSoyez exclusif IFF $ Y_1 $ correspond à littéral $ A $ A $ et $ y_2 $ correspond à littéral $ \ overline {A} $ .

.