Aniello Murano » 17.Esercitazione su problemi NP-Completi

DOUBLE-SAT

DOUBLE-SAT = { θ | θ è una formula Booleana con due assegnamenti di soddisfacibilità}.
Si mostri che DOUBLE-SAT è NP-Complete. (Hint: Si usi una riduzione da SAT.)

1. DOUBLE-SAT ∈ NP. Basta indovinare non deterministicamente due differenti assegnamenti di verità per le variabili e verificare che in entrambi i casi la formula è vera
2. Per l’hardness usiamo una riduzione da SAT a DOUBLE-SAT:

• Data una formula θ, definiamo una nuova formula θ’ ottenuta da θ aggiungendo in congiunzione la clausola (x v x), dove x è una variabile non appartenente a θ.
• Chiaramente la riduzione è polinomiale.
• Resta da dimostrare che θ ∈ SAT se e solo se θ’ ∈ DOUBLE-SAT
• Se θ non è soddisfacibile, anche θ’ è insoddisfacibile. Dunque θ not in SAT → θ’ not in DOUBLE-SAT
• Se θ è soddisfacibile, allora possiamo usare gli stessi assegnamenti di verità per dire che θ’ è soddisfacibile. Inoltre, sia per x = 0 che per x = 1 la formula resta soddisfacibile.
• Dunque θ ∈ SAT → θ’ ∈ DOUBLE-SAT.

SET-PARTITION

Il problema SET-PARTITION prende in input un insieme S di numeri e decide se l’insieme può essere partizionato in due insiemi A e il suo complemento

Si mostri che SET-PARTITION è NP-Complete.
Per l’appartenenza a NP mostriamo che esiste una macchina di Turing nondeterministica che in tempo polinomiale decide il problema:
Basta fare un “guess” su due partizioni e verificare che hanno la stessa somma
Per l’hardness usiamo una riduzione polinomiale dal problema SUBSET-SUM, in modo tale che il problema SET-PARTITION ammette soluzione se e solo se SUBSET-SUM ammette soluzione

SET-PARTITION (segue)

Si ricordi che SUBSET-SUM è definito nel modo seguente:
Dato un insieme S di interi e un numero target t, occorre verificare che esiste un sottoinsieme di numeri di S la cui somma è uguale a t
Sia s la somma degli elementi di S.
Consideriamo due casi distinti.
Se s = 2t, usiamo come input per il SET-PARTITION l’insieme S stesso. Ovviamente, S appartiene a SET-PARTITION se e solo se (S, t) è in SUBSET-SUM.
Se s è diverso da 2t, usiamo come input per SET-PARTITION l’insieme S’ = S U {2s, s+2t}. Si noti che la somma di tutti gli oggetti in S’ è 4s + 2t.
Si supponga adesso che (S, t) sia in SUBSET-SUM. Allora, esiste un sottoinsieme A di S’ la cui somma è t. Sia A’ = A U {2s}. Con semplici calcoli si vede che la somma degli elementi in A’ e il suo complemento rispetto S’ coincide. Dunque, S’ è in SET-PARTITION.
Si supponga adesso che S’ sia partizionato in due insiemi: A’ e il suo complemento. Per ognuno di questi insiemi, la somma dei suoi elementi è 2s+t. Si noti adesso che gli elementi 2s e s+2t non possono stare nello stesso insieme perchè la loro somma è maggiore di 2s+t.
Senza perdita di generalità, si assuma che 2s è in A’.
Sia adesso A uguale ad A’ \ {2s}. Allora la somma di tutti gli elementi di A è 2s+t-2s=t e tutti gli elementi di A sono elementi di S. Dunque, (S,t) è in SUBSET-SUM

SUBSET-SUM-k è NP-Completo

Sia SUBSET-SUM-k = { | S è un insieme di interi positivi che contiene un sottoinsieme B di taglia k tale che è in SUBSET-SUM}
Si provi che SUBSET-SUM-k è NP-Complete usando per l’harndess una riduzione da SUBSET-SUM.
SUBSET-SUM-k is in NP since we can verify that a subset of size k adds up to the target t. Now, we will show that SUBSET-SUM-k is also NP-Complete.
Consider an instance of SUBSET-SUM with the set S = {x1, x2, … xn} and a target T. Let X = x1 + x2 + … +xn. Here is an instance of SUBSET-SUM-k that is accepted if and only if the original instance of SUBSET SUM is:
S” = {X, X, … X, X – x1, X – x2, … X – xn}, T_ = nX – T, k = n
In particular, our set S” has 2n elements in it: n X_s and then one element corresponding to each element in the original set S. First of all, IF there is a subset in S that adds up to T, we can find a subset of S” of size n that adds up to T”. (To do this, simply pick each term of the form X – xi, that corresponds to the elements in the subset of S that add up to T. Then pick the remainder of the elements to be S”s.

SUBSET-SUM-k è NP-Completo (segue)

Based on this construction, the sum will be:
X + X + … + (X – xi), for each xi in the original subset adding up to T.
= nX – (xi, for each xi in the original subset adding up to T.)
= nX – T
= T”, as desired.
Now, we must show the other direction. If there is a subset in S_ of size n that adds up to T”, then there will be a subset in S that adds up to T. Consider any subset of T” of size n that adds up to nX – T. Naturally, some of these values, say m of them, will be X, while the other n – m will be of the form X – xi. Adding these up we get that
mX + (n – m)X – (the sum of n – m xis) = nX – T.
Simplifying, we find that
(the sum of n – m xis) = T, but this implies that there is a subset of S such the sum of its elements equals T, as desired.
Thus, we have shown how to reduce SUBSET-SUM to SUBSET-SUM-k and can conclude that SUBSET-SUM-k is NP-Complete.

Il problema del Triangolo in un Grafo (3-CLIQUE)

Un triangolo in un grafo indiretto è una 3-clique. Si mostri che il problema di verificare che un grafo abbia un triangolo è in P. Formalmente, il problema è così definito:

TRIANGLE = { | G contiene una 3-clique}

Per mostrare che TRIANGLE è in P è sufficiente mostrare un algoritmo che risolve il problema in tempo polinomiale nella taglia dell’input.
Dato un grafo di n vertici, iteriamo sulle n3 combinazioni di 3 vertici in G.
Per ogni combinazione, controlliamo se tutti gli archi sono presenti.
Se e solo se esiste una combinazione per cui il controllo sugli archi risponde affermativamente, allora rispondiamo “SI” al problema.
Questo algoritmo risolve correttamente il problema TRIANGLE con un algoritmo di forza bruta che prende tempo O(n³). Si noti che verificare l’esistenza dei 3 archi richiede tempo O(1) time.
Quindi, TRIANGLE è in P.
Esercizio per gli studenti: PENT = { | G contiene una 5-clique} è in P?

Half-Clique è NP-Completo

Sia HALF-CLIQUE = { | G è un grafo inderetto di n nodi e (G, n/2) è una CLIQUE}. Si mostri che HALF-CLIQUE è NP-completo.
Per l’appartenenza in NP, usiamo l’algoritmo di verifica per k-Clique, già usato in precedenza, per k qualsiasi.
Per la NP-hardness, usiamo una riduzione da k-CLIQUE a HALF-CLIQUE in tempo polinomiale.
Dividiamo la riduzione in due parti:
Se k ≥ n/2, allora si procede come segue:

1. Si costruisce da G un nuovo grafo G’ aggiungendo 2k – n vertici, tutti senza archi uscenti (cioè tutti i nodi aggiunti sono disconnessi in G’).
2. G’ ha n+(2k–n) = 2k vertici ed è in HALF-CLIQUE se e solo se ha una k-Clique.

Half-Clique è NP-Completo (segue)

Se k < n/2, allora si procede come segue:

1. Si costruisce da G un nuovo grafo G’ aggiungendo ai suoi vertici V, un insieme di n-2k vertici V’. Così facendo, G’ ha n+n–2k = 2n–2k = 2(n-k) vertici.
2. Si collegano tutte le coppie di vertici in V’ in modo che formino una (V’, n-2k)-Clique.
3. Si collegano poi tutti i vertici in V con quelli in V’.
4. Se G ha una k-clique, allora G’ deve avere una Clique di taglia k+(n–2k)=n–k, perché tutti i k vertici in G formano una clique e sono connessi a n–2k veritici in V’ che formano una clique e tutti questi sono, a loro volta, collegati tra loro.
5. Se G’ ha una Clique ti taglia n – k, allora G’ appartiene ad HALF-CLIQUE. Si noti che se G non ha una k-clique, allora è impossibile avere una (n-k)-Clique in G’.