Équivalence entre min non coupé et min-csp_xor

Question

dans cet article

Agarwal, Amit, et al. "O (√ journal n) Algorithmes d'approximation pour min Min Non coupé, Min 2cnf Deltetion et problèmes de coupe dirigés." Procédure du trente-septième Symposium ACM annuel sur la théorie de l'informatique. 2005.

agarwal et al. affirmer que les deux problèmes suivants sont équivalents.

considère les variables booléennes $ b_1, \ dots, b_n $ et un ensemble de contraintes du formulaire $ b_i \ oplus b_j= 0 $ et $ b_i \ oplus b_j= 1 $ . L'objectif est de minimiser le nombre de contraintes non satisfaites.

et

donné un graphique $ g= (v, e) $ Trouvez une coupe qui minimise le nombre de bords non coupés.

Si les contraintes étaient seulement de la forme $ b_i \ oplus b_j= 1 $ , l'équivalence est simple. Toutefois, si nous considérons également des contraintes de la forme $ b_i \ oplus b_j= 0 $ , la première formulation me semble plus générale.

Comment vont ces équivalents?

Answer 1

Supposons que nous soyons un ensemble de contraintes de la forme $ b_i \ oplus b_j= C $ . Nous construisons un graphique avec un sommet correspondant à chaque $ b_i $ . Pour chaque contrainte de la forme $ b_i \ oplus b_j= 1 $ , nous ajoutons un bord $ \ {i, j \ {i, j } $ . Pour chaque contrainte de la forme $ b_i \ oplus b_j= 0 $ , nous ajoutons un nouveau sommet $ x / span >, et deux bords $ \ {i, x \}, \ {j, x \} $ .

.

Nous pouvons penser à une coupe comme une partition des sommets en deux parties. Pour une contrainte de la forme $ b_i \ oplus b_j= 1 $ , la contrainte est insatisfaite IFF $ i, j $ < / Span> appartiennent à la même partie IFF $ \ {i, J \} $ est non coupé. Pour une contrainte de la forme $ b_i \ oplus b_j= 0 $ , il y a deux cas:

• Si la contrainte n'est pas satisfaite, alors $ i, j $ appartient à différentes pièces, et donc exactement l'un des bords $ \ {i, x \}, \ {j, x \} $ est non coupé.

• Si la contrainte n'est pas insatisfait, alors $ i, j $ appartenez à la même pièce, et donc (selon l'emplacement de la localisation de $ x $ ) zéro ou deux des bords $ \ {i, x \}, \ {j, x \} $ < / span> sont non coupés. Étant donné que nous visons de minimiser le nombre de bords non coupés, nous pouvons supposer que zéro sont non coupés.

Au total, le nombre de contraintes non satisfaites est la même que le nombre de bords non coupés.