Abbinamento perfetto nel grafico bipartite con bordi reciprocamente esclusivi

Question

Problema

Vorrei risolvere perfetto corrispondenza nel problema del grafico bipartite dove alcuni bordi sono reciprocamente esclusivi .

Esempio

Verticolari sinistro: $ A, B, c $

Vertici giusti: $ x, y, z $

Bordi: $ (A, X), (A, Y), (B, Z), (c, y) $

coppie esclusive: $ (B, z) $ e $ (c, y) $ .

Risposta: nessuna corrispondenza perfetta

Domanda

è il problema in p o np ?

tentativi di soluzione

So che perfetto corrispondenza nel problema del grafico bipartite è in p .Ma non riesco a trovare un algoritmo polinomiale per la versione sopra di questo problema.Ho anche provato a dimostrare che è np , ma senza fortuna.

Answer 1

è $ NP $ come $ sab $ può essere ridotto polinomiamente a questo problema.

.

Lascia che le clausole siano i vertici parte sinistro e i letterali sono i vertici di parte giusta.Disegna un bordo $ (x, y) $ Clausola IFF $ x $ contiene letterale $ y $ .Infine, una coppia di bordi $ (x_1, y_1) $ e $ (x_2, y_2) $ Sii esclusivo IFF $ Y_1 $ corrisponde alla letterale $ a $ e $ y_2 $ corrisponde alla letterale $ \ overline {A} $ .