Нахождение соответствия, сжатие которого минимизирует количество дуг в графе

Для смешанного графа с ребрами E и дугами A найдите совпадение в E, которое минимизирует количество дуг в G / M , где G / M получается из G путем сжатия совпадающих вершин и удаления параллельные дуги.$G=(V,E,A)$$E$$A$$E$$G/M$$G/M$$G$

Является ли (вариант решения) этой проблемой NP-полной? Было ли это изучено в литературе?

Я не знаю, является ли ваше намерение позволить параллельным ребрам в E и дугам в A быть параллельными или нет, но в конце это не имеет значения. В этом ответе мы предполагаем, что вы не позволяете ребрам и дугам быть параллельными.

Рассмотрим особый случай, когда для каждой дуги в A , A также содержит дугу в противоположном направлении. В этом случае мы можем игнорировать ориентацию дуг и считать их ненаправленными. Мы называем ребра в E черными ребрами, а ребра в A красными ребрами .

$x_1,\dots,x_n$$v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$$(v_i,x_i)$$(v_i,\bar{x}_i)$$5\binom{n}{2}-m$$v_i$$v_j$$x_i$$x_j$$(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$$l$и красным краем тогда и только тогда, когда предложение не появляется в φ .$l'$$(\bar{l}\vee\bar{l}')$

Понятно, что мы должны учитывать только максимальные совпадения на черных краях, чтобы минимизировать количество красных краев после сжатия. Также ясно, что каждое максимальное совпадение M в черных ребрах состоит из n ребер, соединяющих с для i = 1,…, n . Определите это максимальное соответствие M с помощью задания истинности . Легко проверить, что после сжатия M и удаления параллельных ребер граф имеет ровно красных ребер, где k$v_i$$l_i\in\{x_i,\bar{x}_i\}$$\{l_1,\dots,l_n\}$$4\binom{n}{2}-k$количество пунктов, удовлетворяемых этим назначением истины. Следовательно, минимизация количества красных ребер после сокращения совпадения по черным ребрам эквивалентна максимизации количества удовлетворенных предложений.