Localizando uma correspondência cuja contração minimiza o número de arcos em um gráfico

Dado um gráfico misto $G=(V,E,A)$ com as arestas $E$ e arcos $A$ , encontre uma correspondência em $E$ que minimize o número de arcos em $G/M$ , onde $G/M$ é obtido de $G$ contratando vértices correspondentes e removendo arcos paralelos.

(A versão de decisão) deste problema está incompleta? Foi estudado na literatura?

Não sei se sua intenção é permitir que as bordas não direcionadas em E e os arcos em A sejam paralelos ou não, mas isso não importa no final. Nesta resposta, assumimos que você não permite que arestas e arcos sejam paralelos.

Considere um caso especial em que para cada arco em A , A também contém o arco na direção oposta. Nesse caso, podemos ignorar a orientação dos arcos e considerá-los não direcionados. Chamamos arestas em E arestas pretas e arestas em A arestas vermelhas .

$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$e por uma borda vermelha se e somente se a cláusula não aparecer em φ .$l'$$(\bar{l}\vee\bar{l}')$

É claro que precisamos considerar apenas as correspondências máximas nas bordas pretas para minimizar o número de bordas vermelhas após a contração. Também está claro que todo M máximo correspondente nas arestas pretas consiste em n arestas conectando a para i = 1,…, n . Identifique esse M máximo correspondente com a atribuição de verdade . É fácil verificar se, após contratar M e remover arestas paralelas, o gráfico possui exatamente arestas vermelhas, onde k$v_i$$l_i\in\{x_i,\bar{x}_i\}$$\{l_1,\dots,l_n\}$$4\binom{n}{2}-k$é o número de cláusulas satisfeitas por essa atribuição de verdade. Portanto, minimizar o número de arestas vermelhas após contratar uma correspondência em arestas pretas é equivalente a maximizar o número de cláusulas satisfeitas.