Equivalencia entre min sin cortar y min-csp_xor

Question

en este documento

agarwal, amit, et al. "O (√ Log n) algoritmos de aproximación para la eliminación mínima de min2cnf, y los problemas de corte dirigidos". Procedimientos del trigésimo séptimo Simposio ACM anual sobre teoría de la computación. 2005.

Agarwal et al. afirmar que los siguientes dos problemas son equivalentes.

Considerar las variables booleanas $ b_1, \ puntos, b_n $ y un conjunto de restricciones del formulario $ b_i \ oplus b_j= 0 $ y $ b_i \ oplus b_j= 1 $ . El objetivo es minimizar el número de restricciones insatisfechas.

y

Dado un gráfico $ g= (v, e) $ Encuentre un corte que minimice el número de bordes sin cortar.

Si las restricciones fueron solo de la forma $ b_i \ oplus b_j= 1 $ , la equivalencia es sencilla. Sin embargo, si también consideramos restricciones de la forma $ b_i \ oplus b_j= 0 $ , la primera formulación me parece más general.

¿Cómo son estos equivalentes?

Answer 1

Supongamos que nos dan un conjunto de restricciones de la forma $ b_i \ oplus b_j= C $ . Construimos un gráfico con un vértice correspondiente a cada $ b_i $ . Para cada restricción del formulario $ b_i \ oplus b_j= 1 $ , agregamos un borde $ \ {i, j \ } $ . Para cada restricción de la forma $ b_i \ oplus b_j= 0 $ , agregamos un nuevo vértice $ x $ , y dos bordes $ \ {I, X \ \ \ \ {J, X \} $ .

Podemos pensar en un corte como una partición de los vértices en dos partes. Para una restricción de la forma $ b_i \ oplus b_j= 1 $ , la restricción es insatisfecha IFF $ < / SPAN> Pertenece a la misma parte IFF $ \ {i, j \} $ es sin cortar. Para una restricción de la forma $ b_i \ oplus b_j= 0 $ , hay dos casos:

• Si la restricción no está satisfecha, entonces $ i, j $ pertenece a diferentes partes, y así exactamente uno de los bordes $ \ {i, x \}, \ {j, x \} $ es sin cortar.

• Si la restricción no está insatisfecha, entonces $ i, j $ pertenece a la misma parte, por lo que (dependiendo de la ubicación de $ x $ ) Cero o dos de los bordes $ \ {i, x \ \ \ \ {J, X \ \ \ \ {J, X \} $ < / span> no son sin cortar. Dado que apuntamos a minimizar el número de bordes sin cortar, podemos asumir que cero son sin cortar.

En total, el número de restricciones insatisfechas es la misma que la cantidad de bordes sin cortar.