Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Complexite parametree (2) :
Recherche de noyaux - bornes superieures
Christophe PAUL
(CNRS - LIRMM)
October 5, 2011Un premier exemple: Vertex Cover
De nitions
Autres exemples de noyaux quadratiques
Regles de reduction en sunflower
Analyse de la structure de la solution par comptage
Programmation lineaire
Regles de reduction globales
Reduction en couronne pour Vertex Cover
Un noyau lineaire pour le Cluster Editing
Un noyau lineaire pour fast a l’aide de couplagesUn premier exemple: Vertex Cover
De nitions
Autres exemples de noyaux quadratiques
Regles de reduction en sunflower
Analyse de la structure de la solution par comptage
Programmation lineaire
Regles de reduction globales
Reduction en couronne pour Vertex Cover
Un noyau lineaire pour le Cluster Editing
Un noyau lineaire pour fast a l’aide de couplages2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)
3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)
Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)
Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)
2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)Regles de reduction pour Vertex Cover
1. Si x est un sommet isole, alors x n’appartient a aucune
solution optimale.
Vertex Cover(G; k) =Vertex Cover(G x; k)
2. Si x est un sommet de degre 1 voisin de y, alors il existe une
solution optimale contenant y.
Vertex Cover(G; k) =Vertex Cover(G f y; xg; k 1)
3. Si x est de degre > k + 1, alors si G possede une
solution de taille k, elle contient le sommet x.
Vertex Cover(G; k) =Vertex Cover(G x; k 1)21. Le graphe reduit possede au plus k ar^etes.
22. Le graphe reduit possede au plus k + k sommets.
Preuve
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.22. Le graphe reduit possede au plus k + k sommets.
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.22. Le graphe reduit possede au plus k + k sommets.
Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.
Si S est un Vertex Cover, alors toute ar^ete est incidente a
un sommet de S.
2Or d(x)6 k et ) k ar^etes au plus.Lemme [Buss]
Si G possede un Vertex Cover de taille k, alors le graphe
2 2reduit possede au plus k + k sommets au plus k ar^etes.
Preuve
21. Le graphe reduit possede au plus k ar^etes.
22. Le graphe reduit possede au plus k + k sommets.