Äquivalenz zwischen min uncout und min-csp_xor

Question

in diesem Papier

Agarwal, Amit et al. "O (√ √ log n) Annäherungsalgorithmen für minis uncut, min 2cnf-Deletion und gerichtete Schnittprobleme." Verfahren des sechsunddreißigjährigen jährlichen ACM-Symposiums zur Computertheorie. 2005.

agarwal et al. behaupten, dass die folgenden zwei Probleme gleichwertig sind.

Erwägen Sie boolesche Variablen $ B_1, \ DOTS, B_N $ und ein Satz von Einschränkungen des Formulars $ b_i \ oplus B_J= 0 $ und $ b_i \ oplus b_j= 1 $ . Ziel ist es, die Anzahl der nicht zufriedenen Einschränkungen zu minimieren.

und

Angesichts eines Diagramms $ g= (V, E) $ Finden Sie einen Schnitt, der die Anzahl der ungeschnittenen Kanten minimiert.

Wenn die Einschränkungen nur des Formulars $ B_I \ oplus b_j= 1 $ waren, ist die Äquivalenz unkompliziert. Wenn jedoch auch Einschränkungen des Formulars $ B_I \ oplus b_j= 0 $ in Betracht ziehen, erscheint die erste Formulierung für mich allgemeiner.

Wie sind diese Äquivalent?

Answer 1

Angenommen, wir erhalten eine Reihe von Einschränkungen des Formulars $ b_i \ oplus b_j= c $ . Wir erstellen ein Diagramm mit einem Scheitelpunkt, der jedem $ B_i $ entspricht. Für jede Einschränkung des Formulars $ b_i \ oplus b_j= 1 $ , fügen wir eine Kante hinzu $ \ {I, J \ } $ . Für jede Einschränkung des Formulars $ b_i \ oplus b_j= 0 $ Hinzufügen eines neuen Scheitelpunkts $ x $ , und zwei Kanten $ \ {i, x \}, \ {j, x \} $ .

Wir können an einen Schnitt als eine Partition der Scheitelpunkte in zwei Teile vorstellen. Für eine Einschränkung des Formulars $ b_i \ oplus b_j= 1 $ ist die Einschränkung nicht zufrieden, iFF $ i, J $ < / Span> Gehören zum selben Teil IFF $ \ {i, j \} $ ist ungeschnitten. Für eine Einschränkung des Formulars $ b_i \ oplus b_j= 0 $ gibt es zwei Fälle:

• Wenn die Einschränkung nicht zufrieden ist, dann gehören $ i, j $ gehören zu verschiedenen Teilen, und so genau einer der Kanten $ \ {i, x \}, \ {j, x \} $ ist ungeschnitten.

• Wenn die Einschränkung nicht unbefriedigt ist, dann gehören $ i, J $ zum selben Teil und so (abhängig vom Standort der $ x $ ) entweder null oder zwei der Kanten $ \ {i, x \}, \ {j, x \} $ < / span> sind ungeschnitten. Da wir darauf abzielen, die Anzahl der ungeschnittenen Kanten zu minimieren, können wir davon ausgehen, dass Null ungeschnitten sind.

Insgesamt ist die Anzahl der unbefriedigten Einschränkungen die gleiche wie die Anzahl der ungeschnittenen Kanten.