Perfeito de correspondência no gráfico bipartido com bordas mutuamente exclusivas

Question

problema

Eu gostaria de resolver correspondência perfeita no problema do gráfico bipartite onde algumas bordas são mutuamente exclusivas .

exemplo

Esquerda vértices: $ a, B, C $

vértices certos: $ x, y, z $

bordas: $ (A, X), (A, Y), (B, Z), (C, Y) $

pares exlusivos: $ (b, z) $ e $ (c, y) $ .

Resposta: Nenhuma correspondência perfeita

pergunta

é o problema em p ou np ?

Tentativas de solução

Eu sei que correspondência perfeita no problema do gráfico bipartido está em p .Mas não consigo encontrar algoritmos de tempo polinômio para a versão acima deste problema.Eu também tentei provar que é np , mas sem qualquer sorte.

Answer 1

É $ NP $ como $ SAT $ pode ser polinomialmente reduzido a este problema.

.

Deixe as cláusulas serem os vértices da parte esquerda, e os literais são os vértices da parte certa.Desenhe uma borda $ (x, y) $ cláusula IFF $ x $ Contém literal $ y $ .Finalmente, um par de arestas $ (x_1, y_1) $ e $ (x_2, y_2) $ Seja exclusivo IFF $ y_1 $ corresponde a literal $ a $ e $ y_2 $ corresponde a literal $ \ overline {a} $ .