Equivalenza tra min Uncut e min-csp_xor

Question

in questo documento

.

Agarwal, Amit, et al. "O (√ log n) Algoritmi di approssimazione per minut min non tagliati, min 2CNF e problemi di taglio diretti." Procedura del trentasettesimo simposio ACM annuale sulla teoria del calcolo. 2005.

Agarwal et al. affermare che i seguenti due problemi sono equivalenti.

.

Considera le variabili booleanetiche $ B_1, \ punti, B_N $ e un insieme di vincoli del modulo $ B_i \ Oplus B_J= 0 $ e $ B_i \ oplus b_j= 1 $ . L'obiettivo è ridurre al minimo il numero di vincoli insoddisfatti.

e

.

Dato un grafico $ G= (V, E) $ Trova un taglio che riduce al minimo il numero di bordi non tagliati.

Se i vincoli fossero solo della forma $ B_i \ oplus b_j= 1 $ , l'equivalenza è semplice. Tuttavia, se consideriamo anche vincoli del modulo $ B_i \ oplus b_j= 0 $ , la prima formulazione mi sembra più generale.

Come sono questi equivalenti?

Answer 1

Supponiamo di ricevere un insieme di vincoli del modulo $ B_i \ oplus b_j= c $ . Costruiamo un grafico con un vertice corrispondente a ciascuna classe $ B_i $ . Per ciascun vincolo della forma $ B_i \ oplus b_j= 1 $ , aggiungiamo un bordo $ \ {i, j \ } $ . Per ciascun vincolo della forma $ B_i \ oplus b_j= 0 $ , aggiungiamo un nuovo vertice $ x $ e due bordi $ \ {i, x \}, \ {j, x \} $ .

Possiamo pensare a un taglio come una partizione dei vertici in due parti. Per un vincolo della forma $ B_i \ oplus b_j= 1 $ , il vincolo è insoddisfatto IFF $ i, J $ < / span> appartengono alla stessa parte IFF $ \ {i, j \} $ è uncut. Per un vincolo della forma $ B_i \ oplus b_j= 0 $ , ci sono due casi:

.

• Se il vincolo non è soddisfatto, allora $ i, j $ appartengono a parti diverse, e così esattamente uno dei bordi $ \ {i, x \}, \ {j, x \} $ è uncut.

• Se il vincolo non è insoddisfatto, quindi $ i, j $ appartengono alla stessa parte, e così (a seconda della posizione della classe $ x $ ) zero o due dei bordi $ \ {i, x \}, \ {j, x \} $ < / span> non sono tagliati. Dal momento che mirano a minimizzare il numero di bordi non tagliati, possiamo supporre che lo zero non sia uncut.

In totale, il numero di vincoli insoddisfatti è lo stesso del numero di bordi non tagliati.