Equivalência entre MIN UNCUT e MIN-CSP_XOR

Question

Nesse artigo

Agarwal, Amit, et al."O (√ algoritmos de aproximação de log n) para Min Uncut, exclusão min 2CNF e problemas de corte direcionados." Anais do trigésimo sétimo simpósio anual da ACM sobre teoria da computação.2005.

Agarwal et al.afirme que os dois problemas a seguir são equivalentes.

Considere variáveis ​​booleanas $b_1,\pontos ,b_n$ e um conjunto de restrições da forma $b_i \oplus b_j = 0$ e $b_i \oplus b_j = 1$.O objetivo é minimizar o número de restrições não satisfeitas.

e

Dado um gráfico $G=(V,E)$ encontre um corte que minimize o número de arestas não cortadas.

Se as restrições fossem apenas da forma $b_i \oplus b_j = 1$, a equivalência é direta.No entanto, se considerarmos também restrições da forma $b_i \oplus b_j = 0$, a primeira formulação parece-me mais geral.

Como eles são equivalentes?

Answer 1

Suponha que recebamos um conjunto de restrições da forma $b_i \oplus b_j = c$.Construímos um gráfico com um vértice correspondente a cada $b_i$.Para cada restrição do formulário $b_i \oplus b_j = 1$, adicionamos uma aresta $\{eu,j\}$.Para cada restrição do formulário $b_i \oplus b_j = 0$, adicionamos um novo vértice $x$, e duas arestas $\{i,x\},\{j,x\}$.

Podemos pensar num corte como uma partição dos vértices em duas partes.Para uma restrição da forma $b_i \oplus b_j = 1$, a restrição é insatisfeita se $eu,j$ pertencem à mesma parte se $\{eu,j\}$ está sem cortes.Para uma restrição da forma $b_i \oplus b_j = 0$, existem dois casos:

• Se a restrição não for satisfeita, então $eu,j$ pertencem a partes diferentes e, portanto, exatamente uma das arestas $\{i,x\},\{j,x\}$ está sem cortes.

• Se a restrição não for insatisfeita, então $eu,j$ pertencem à mesma parte, e assim (dependendo da localização de $x$) zero ou duas das arestas $\{i,x\},\{j,x\}$ estão sem cortes.Como pretendemos minimizar o número de arestas não cortadas, podemos assumir que zero não são cortadas.

No total, o número de restrições não satisfeitas é igual ao número de arestas não cortadas.