Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD Optimisation Combinatoire Louis Dublois louis.dublois@gmail.com Université P

TD Optimisation Combinatoire Louis Dublois louis.dublois@gmail.com Université Paris-Dauphine 2020/2021 1 / 64 TD 8 (Correction DM) 2 / 64 E3SAT 3SAT : Un ensemble X de n variables binaires x1, . . . , xn, et une formule φ qui est la conjonction de m clauses C1, . . . , Cm, chacune composée d’au plus 3 litéraux. E3SAT : Restriction du problème 3SAT où chaque clauses Cj contient exaxctement 3 litéraux. Existe-t-il une aﬀectation des valeurs true et false aux variables de X telle que φ est satisfaite ? 3 / 64 E3SAT ∈NP 1) Montrer que E3SAT est dans NP. 4 / 64 E3SAT ∈NP Input : Une formule φ de n variables x1, . . . , xn et m clauses C1, . . . , Cm (chacune composée d’exactement 3 litéraux), et une aﬀectation ρ des variables de φ. Output : Oui si ρ satisfait φ, sinon Non. Pour toute clause Cj dans φ faire : b ←false Pour toute variable x dans Cj faire : Si ρ(x) satisfait Cj faire : b ←true Si b == false faire : Retourner Non Retourner Oui Vériﬁe si ρ satisfait φ en temps O(m). Theorem E3SAT est dans NP 5 / 64 3SAT ≤T E3SAT 2) Créer une réduction polynomiale de Turing 3SAT ≤T E3SAT et présenter cette réduction sous forme d’algorithme. 6 / 64 3SAT ≤T E3SAT Soit φ une instance de 3SAT avec n variables x1, . . . , xn et m clauses C1, . . . , Cm. On veut construire une instance φ′ de E3SAT, i.e. où chaque clause de φ′ a exactement 3 litéraux. Pour toute clause Cj de φ : Si |Cj| = 3, OK. Si |Cj| = 2, i.e. Cj = (x1 ∨x2), alors on supprime Cj et on ajoute les deux clauses : (x1 ∨x2 ∨y) ∧(x1 ∨x2 ∨y). Si |Cj| = 1, i.e. Cj = (x), alors on supprime Cj et on ajoute les quatre clauses : (x ∨y1 ∨y2) ∧(x ∨y1 ∨y2) ∧(x ∨y1 ∨y2) ∧(x ∨y1 ∨y2). 7 / 64 3SAT ≤T E3SAT Input : Une formule φ de 3SAT composé de n variables x1, . . . , xn et m clauses C1, . . . , Cm. Output : Une instance φ′ de E3SAT φ′ ←φ Pour toute clause Cj dans φ faire : Si |Cj| = 2 (Cj = (x1 ∨x2)) faire : Créer C 1 j = (x1 ∨x2 ∨y) et C 2 j = (x1 ∨x2 ∨y) φ′ ←(φ′ \ Cj) ∪{C 1 j ∪C 2 j } Si |Cj| = 1 (Cj = (x)) faire : Créer C 1 j = (x ∨y1 ∨y2), C 2 j = (x ∨y1 ∨y2), C 3 j = (x ∨y1 ∨y2) et C 4 j = (x ∨y1 ∨y2) φ′ ←(φ′ \ Cj) ∪{C 1 j , C 2 j , C 3 j , C 4 j } Retourner φ′ Algorithme en O(m). 8 / 64 Exactitude 3SAT ≤T E3SAT 3) Prouver que cette réduction est correcte. 9 / 64 Exactitude 3SAT ≤T E3SAT Démonstration. Supposons que φ est satisﬁable. Considérons n’importe quelle clause Cj de φ. Si |Cj| = 3, alors Cj est aussi satisﬁable dans φ′. Si |Cj| = 2, alors x1 ou x2 satisfait Cj, et les deux clauses C 1 j et C 2 j sont satisfaites dans φ′. Si |Cj| = 1, alors x satisfait Cj, et les quatre clauses C 1 j , . . . , C 4 j sont satisfaites dans φ′. Donc φ′ est satisfaite. 10 / 64 Exactitude 3SAT ≤T E3SAT Démonstration. Supposons que φ′ est satisfaite. Considérons n’importe quelle clause Cj de φ′. Si Cj ∈φ, alors Cj est satisfaite dans φ. Si Cj est telle qu’il existe C ′ j où Cj et C ′ j ont été créées par l’algorithme à partir de C ∗ j . Alors Cj = (x1 ∨x2 ∨y) et C ′ j = (x1 ∨x2 ∨y). La variable y ne peut pas satisfaire Cj et C ′ j donc x1 ou x2 satisfait Cj et C ′ j . Donc la clause originale C ∗ j est satisfaite dans φ. Si Cj est telle qu’il existe C 2 j , C 3 j , C 4 j où Cj, C 2 j , C 3 j , C 4 j ont été créées par l’algorithme à partir de C ∗ j . Les deux variables ajoutées y1 et y2 ne peuvent pas satisfaire les quatre clauses Cj, C 2 j , C 3 j , C 4 j , donc la variable x les satisfait. Donc C ∗ j est satisfaite dans φ. Donc φ est satisfaite. 11 / 64 E3SAT est NP-complet 4) Déduire que le problème E3SAT est NP-complet. 12 / 64 E3SAT est NP-complet Du fait que le problème 3SAT est NP-complet, et par les deux directions de la preuve de la question 3), on a que : E3SAT est NP-diﬃcile. Par la question 1), on a que E3SAT est dans NP. Par ces deux résultats, on a : Theorem E3SAT est NP-complet. 13 / 64 Minimum Set Cover Ensemble U = {u1, . . . , un} d’éléments. Famille S = {S1, . . . , Sm} de sous-ensembles de U : pour tout ensemble Sj ∈S, Sj ⊆U. Trouver une sous-famille S∗de S de taille minimum qui couvre tous les éléments de U ? 14 / 64 k-Set Cover 1) Donner la version décision k-Set Cover du problème Minimum Set Cover. 15 / 64 k-Set Cover Ensemble U = {u1, . . . , un} d’éléments. Famille S = {S1, . . . , Sm} de sous-ensembles de U : pour tout ensemble Sj ∈S, Sj ⊆U. Entier k ≤m. Existe-t-il une sous-famille S∗⊆S de taille au plus k qui couvre tous les éléments de U ? 16 / 64 k-Set Cover ∈NP 2) Montrer que k-Set Cover est dans NP (on peut supposer ici que n et m sont des polynômes l’un de l’autre). 17 / 64 k-Set Cover ∈NP Input : Une instance ((U, S), k) de k-Set Cover avec |U| = n, |S| = m, et k ≤m, et une sous-famille S∗de S. Output : Oui si S∗est un set cover de taille au plus k, sinon Non. Pour tout u ∈U faire : b ←false Pour tout S ∈S∗faire : Si u ∈S faire : b ←true Si b == false faire : Retourner Non Si |S∗| ≤k faire : Retourner Oui Retourner Non Vériﬁe si S∗est un set cover de taille au plus k en temps O(nm). Theorem k-Set Cover est dans NP 18 / 64 k-Dominating Set ≤T k-Set Cover 3) Créer une réduction polynomiale de Turing Π ≤T k-Set Cover, où Π est un problème de graphe NP-complet que l’on a vu en TD et Π ̸= k-Vertex Cover. 19 / 64 k-Dominating Set ≤T k-Set Cover Soit (G = (V , E), k) une instance de k-Dominating Set avec |V | = n, |E| = m et k ≤n. On veut construire une instance ((U, S), k′) de k′-Set Cover : Pour tout sommet u ∈V : On rajoute u dans U. Pour tout sommet u ∈V : On rajoute l’ensemble Su = N[u] dans S. On pose k′ = k. 20 / 64 Exactitude k-Dominating Set ≤T k-Set Cover 4) Prouver que cette réduction est correcte. 21 / 64 Exactitude k-Dominating Set ≤T k-Set Cover Démonstration. Supposons qu’il existe un dominating set D ⊆V dans G de taille au plus k. On pose S∗= {N[u] ∈S : u ∈D}. Pour tout u ∈V , on a : soit u ∈D ; soit il existe v ∈N(u) ∩D. Donc S u∈D N[u] = V = U. Donc S S∈S∗S = U. Donc S∗est un set cover de (U, S) de taille au plus k. 22 / 64 Exactitude k-Dominating Set ≤T k-Set Cover Démonstration. Supposons qu’il existe un set cover S∗⊆S dans (U, S) de taille au plus k. On pose D = {u ∈V : N[u] ∈S∗}. Pour tout u ∈U, on a : il existe S ∈S∗tel que u ∈S. Donc S S∈S∗S = U = V . Donc S u∈D N[u] = V . Donc D est un dominating set de G de taille au plus k. 23 / 64 k-Set Cover est NP-complet 5) Déduire que le problème k-Set Cover est NP-complet. 24 / 64 k-Set Cover est NP-complet Du fait que le problème k-Dominating Set est NP-complet, et par les deux directions de la preuve de la question 4), on a que : k-Set Cover est NP-diﬃcile. Par la question 2), on a que k-Set Cover est dans NP. Par ces deux résultats, on a : Theorem k-Set Cover est NP-complet. 25 / 64 |U| = O(|S|) 6) Expliquer pourquoi k-Set Cover reste NP-complet même lorsque |U| = O(|S|2) (voir même |U| = O(|S|) si vous pouvez). 26 / 64 |U| = O(|S|) Dans notre réduction, uploads/Litterature/ td8-optimisation-combinatoire.pdf