d-extensibles, d-bloqueurs et d-transversaux de problèmes d’optimisation combinatoire

 Notions générales de théorie des graphes

Cette section présente des notions classiques de théorie des graphes. Les notations proviennent de [42] (Picouleau, Faure, Lemaire) et de [71] (Schrijver). Un graphe non orienté G est défini par un ensemble de sommets V et un ensemble d’arêtes E qui est un ensemble de paires non ordonnées d’éléments distincts de V . On notera G “ pV, Eq. Les arêtes tu, vu où u P V et v P V pourront être notés uv ou vu. Si uv P E alors les sommets u et v sont dits adjacents ou voisins. Pour tout sommet u P V on note Γpuq l’ensemble de ses voisins et on note δGpuq le nombre de ses voisins qu’on nomme le degré du sommet. Pour tout sous-ensemble Vˆ Ă V on note ΓpVˆ q l’ensemble des voisins des sommets de Vˆ qui n’appartiennent pas à Vˆ . Une chaîne entre deux sommets u et v d’un graphe est un ensemble de sommets successifs et distincts v0v1..vk tel que v0 “ u, vk “ v et @i P rr1, kss, vi´1vi P E. La longueur d’une chaîne est le nombre d’arêtes de la chaîne. Un graphe est dit connexe s’il existe une chaîne entre tout couple de sommets. Un cycle est une chaîne dont le premier élément est 19 aussi le dernier donc si vk “ v0. Un graphe Gˆ “ pV , ˆ Eˆq est appelé un sous-graphe de G “ pV, Eq induit par Vˆ si Vˆ Ď V et Eˆ “ tuv P E, u P V , v ˆ P Vˆ u. On note GrVˆ s le sous-graphe de G induit par Vˆ . Un graphe Gˆ “ pV, Eˆq est appelé un graphe partiel de G “ pV, Eq si Eˆ Ĺ E. Un ensemble stable S Ă V de G, aussi appelé stable ou ensemble indépendant, est un ensemble de sommets qui pris deux à deux sont non adjacents. On note αpGq le cardinal maximal d’un stable de G. Considérons le problème STABLE suivant : — Instance : Un graphe G “ pV, Eq, un entier positif k ď |V | — Question : Est-ce que G contient un stable S de taille k ou plus ? Le problème STABLE est NP-complet [46]. On définit une partition de l’ensemble des sommets de G : — Les sommets forcés sont les sommets qui appartiennent à tous les stables de cardinal maximal de G. L’ensemble des sommets forcés est noté ΞpGq. Le nombre de sommets forcés est noté ξpGq “ |ΞpGq|. — Les sommets exclus sont les sommets qui n’appartiennent à aucun stable de cardinal maximal de G. L’ensemble des sommets exclus est noté ΨpGq. Le nombre de sommets exclus est noté ψpGq “ |ΨpGq|. — Les sommets libres sont les sommets qui ne sont ni forcés ni exclus. L’ensemble des sommets libres est noté ΦpGq. Le nombre de sommets libres est noté φpGq “ |ΦpGq|. L’ensemble des sommets forcés est parfois noté core(G) et l’union des sommets forcés et des sommets libres est noté corona(G) [20]. Un couplage C Ă E de G est un ensemble d’arêtes qui n’ont aucune extrémité commune. On note µpGq le cardinal maximal d’un couplage de G. Pour tout couplage M, on note V pMq l’ensemble des sommets du graphe incidents à une arête de M. Considérons le problème COUPLAGE suivant : — Instance : Un graphe G “ pV, Eq, un entier positif k ď |V | 20 — Question : Est-ce que G contient un couplage M de taille k ou plus ? Le problème COUPLAGE est polynomial [40]. On définit une partition de l’ensemble des arêtes de G : — Les arêtes forcées sont les arêtes qui appartiennent à tous les couplages de cardinal maximal de G. L’ensemble des arêtes forcées est noté Ξ1 pGq. Le nombre d’arêtes forcées est noté ξ 1 pGq “ |Ξ 1 pGq|. — Les arêtes exclues sont les arêtes qui n’appartiennent à aucun couplage de cardinal maximal de G. L’ensemble des arêtes exclues est noté Ψ1 pGq. Le nombre d’arêtes exclues est noté ψ 1 pGq “ |Ψ1 pGq|. — Les arêtes libres sont les arêtes qui ne sont ni forcées ni exclues. L’ensemble des arêtes libres est noté Φ1 pGq. Le nombre d’arêtes libres est noté φ 1 pGq “ |Φ 1 pGq|. Un graphe est dit biparti si V peut être séparé en deux ensemble disjoints B et R tels que chacun de ces ensembles forme un stable. Autrement dit, chaque arête de E a pour extrémités un sommet de B et un sommet de R. On peut aussi définir les graphes bipartis comme des graphes sans cycle de longueur impaire. On note G “ pB, R, Eq un graphe biparti. Un arbre est un graphe connexe et sans cycles. Notons qu’un arbre est un graphe biparti. Le graphe complémentaire d’un graphe G “ pV, Eq est le graphe G “ pV, Eˆq tel que Eˆ “ tij, ij R Eu. Un graphe G “ pV, Eq est dit orienté si les éléments de E sont des couples ordonnés de sommets. On nomme alors arcs les éléments de E. Étant donnés deux sommets u P V et v P V , on note pu, vq l’arc d’origine u et d’extrémité v. Un chemin entre deux sommets u et v d’un graphe orienté est un ensemble de sommets successifs v0v1..vk tel que v0 “ u, vk “ v et @i P rr1, kss, vi´1vi P E. La longueur d’un chemin est le nombre d’arcs du chemin. Un circuit est un chemin dont le premier élément est aussi le dernier donc si vk “ v0. Une arborescence est obtenue en orientant un arbre de façon à ce qu’il existe un sommet 21 r tel que pour tout sommet x P V du graphe, il existe un chemin de r à x. Le sommet r est appelé la racine de l’arborescence. 

Une caractérisation des stables dans les graphes bipartis

Nous présentons ici une caractérisation des stables de cardinal maximal issue de [17] qui sera utilisée dans les sections suivantes. Soit w : V Ñ N une fonction de poids des sommets d’un graphe G “ pV, Eq. Soit Vˆ Ă V un sous-ensemble de sommets. On note wpVˆ q la somme des poids des éléments de Vˆ . On considère le problème STABLEW de recherche de stables de poids maximal : — Instance : Un graphe G “ pV, Eq, une fonction de poids w : V Ñ N, un entier positif k ď wpV q — Question : Est-ce que G contient un stable S tel que wpSq ě k ? Remarquons que le problème STABLE correspond au problème STABLEW dans le cas où @x P V , wpxq “ 1. On note αwpGq le poids maximal d’un stable de G. Propriété 1.2.1. [17] Soit un graphe biparti G “ pB, R, Eq. Tous les sommets de G sont libres si et seulement si αwpGq “ wpBq “ wpRq. Corollaire 1.2.1. [17] Si @x P V , wpxq “ 1 alors les sommets de G sont libres si et seulement si µpGq “ αpGq “ φpGq 2 “ |BYR| 2 . Donc G admet un couplage parfait. Propriété 1.2.2. [17] Soit un graphe biparti G “ pB, R, Eq dont tous les sommets sont libres. Il existe une partition maximale tV1, …, VKu des sommets de G telle que wpBXViq “ wpR X Viq et pour tout stable de poids maximal S ˚ de G, soit S ˚ X Vi “ R X Vi, soit S ˚ X Vi “ B X Vi. On note Ci “ GrVis le sous-graphe de G induit par l’ensemble Vi . Le sous-graphe Ci est appelé une composante de G. Propriété 1.2.3. [17] Une composante Ci de G admet exactement deux stables de poids maximal : Vi X B et Vi X R. 22 Construisons le graphe orienté Gc “ pVc, Acq de la façon suivante : chaque sommet de Vc porte le nom d’une composante de G : Vc=tCi @i “ 1..Ku et Ac “ tpCi , Cj q @i ‰ j il existe xy P E avec x P Vi XB et y P Vj XR u. Ce graphe est appelé graphe des composantes de G. Propriété 1.2.4. [17] Gc est un graphe sans circuits. Pour tout sommet x de G on note Cpxq la composante qui contient le sommet x. Soient deux composantes Cpxq et Cpyq de Gc. On note Cpxq Ñ Cpyq le fait qu’il existe un chemin de Cpxq à Cpyq dans Gc, le chemin pouvant être de longueur nulle si Cpxq “ Cpyq. On note V pCiq l’ensemble des sommets contenus dans la composante Ci . Propriété 1.2.5. [17] Soient S ˚ un stable de cardinal maximal de G et x et y deux sommets de S ˚ tels que Cpxq Ñ Cpyq. Si x P B alors y P B. Si y P R alors x P R. Corollaire 1.2.2. [17] Soient deux composantes Cpxq et Cpyq de G. Si Cpxq Ñ Cpyq alors tout stable optimal S ˚ tel que S ˚ X V pCpxqq Ĺ B vérifie S ˚ X V pCpyqq Ĺ B. Corollaire 1.2.3. [17] Soient S ˚ un stable de cardinal maximal de G et x et y deux sommets de G tels que Cpxq Ñ Cpyq. Si x P B X S ˚ et y P R, alors y R S ˚ et si x P R et y P B alors S ˚ X tx, yu ‰ H. Dans la suite de cette section, on considérera le cas où les poids des sommets de G sont unitaires. Dans ce cas, la partition des sommets de G correspond aux composantes connexes du graphe partiel G “ pV, E ´ Ψ1 pGqq. On peut définir l’ensemble des arcs du graphe des composantes ainsi : Ac “ tpCi , Cj q @i ‰ j , Dxy P Ψ1 pGq, x P V pCiq X B, y P V pCj q X Ru. On a aussi la propriété suivante : Propriété 1.2.6. [17] Soit g “ pB, R, Eq un graphe biparti dont tous les sommets sont libres. Toute composante de G admet un couplage parfait. Exemple 1.2.1. Appliquons la caractérisation sur le graphe biparti G “ pB, R, Eq de la Figure 1.1. Les sommets de B sont les losanges et les sommets de R sont les cercles. Tout d’abord, on commence par identifier et retirer les arêtes exclues. Elles sont en pointillé dans la Figure 1.2. Après le retrait, on obtient la Figure 1.3. Les composantes connexes du graphe de la Figure 1.3 correspondent aux composantes du graphe G. 23 On construit ensuite le graphe des composantes de G. Comme indiqué sur la Figure 1.3, le graphe contient quatre composantes.Les sommets du graphe des composantes correspondent aux composantes et sont indiqués dans la Figure 1.4. Les arcs du graphe des composantes correspondent aux arêtes exclues de G. Il y a ici trois arêtes exclues. L’arête ah correspond à un arc entre la composante Caf et la composante Cch. L’arête bj correspond à un arc entre la composante Cbg et la composante Cdeij . L’arête ci correspond à un arc entre la composante Cch et la composante Cdeij . Le graphe des composantes est indiqué dans la Figure 1.5. D’après la caractérisation, tout stable de cardinal maximal qui contient un sommet de B doit contenir les sommets de B des composantes successeurs. Ainsi, si un stable de cardinal maximal contient le sommet a, il doit aussi contenir les sommets de B des composantes successeurs donc il doit contenir les sommets c, d et e. Dans la suite du document, on utilisera les conventions suivantes pour les figures des graphes bipartis. Les sommets de B seront des losanges, les sommets de R seront des cercles. Si deux sommets sont reliés par une arête, c’est qu’ils sont dans la même composante. Si deux sommets sont reliés par un arc, c’est qu’il existe un arc entre les deux composantes dans le graphe des composantes. De cette façon, on peut représenter en une figure un graphe et son graphe des composantes. La Figure 1.6 applique cette représentation au graphe de l’exemple précédent et fait apparaître les composantes dans des cercles. Ainsi, le graphe de l’exemple sera représenté par le graphe de la Figure 1.7. Le graphe des composantes est sans circuits, il peut donc être organisé en niveaux tel que le premier niveau contient les composantes sans prédécesseurs dans le graphe des composantes. On numérote les composantes par ordre croissant à partir du premier niveau. Par exemple, dans la figure 1.5, les composantes CAF et CGB sont de niveau 1, la composante CCH est de niveau 2 et la composante CDEIJ est de niveau 3. Appliquons maintenant cette caractérisation dans les arbres. Soit un arbre G “ pB, R, Eq. Propriété 1.2.7. Le graphe Gc est un arbre orienté. 24 a b c d e f g h i j Figure 1.1 – Un graphe biparti a b c d e f g h i j Figure 1.2 – Graphe biparti où les arêtes exclues sont en pointillés a b c d e f g h i j Figure 1.3 – Graphe biparti sans les arêtes exclues Caf Cbg Cch Cdeij Figure 1.4 – Sommets du graphe des composantes Caf Cbg Cch Cdeij Figure 1.5 – Graphe des composantes 25 f a g b h c i d j e Figure 1.6 – Représentation du graphe avec les composantes visibles f a g b h c i d j e Figure 1.7 – Représentation du graphe et de son graphe des composantes Propriété 1.2.8. Soit G “ pB, R, Eq un arbre dont tous les sommets sont libre. Les composantes Ci de G sont telles que |V pCiq X B| “ 1, et |V pCiq X B| “ 1. De plus, si on note u et v les sommets de Ci, alors uv P E. Démonstration. G est un arbre dont tous les sommets sont libres. Il admet donc un unique couplage parfait. Chaque composante n’est donc constituée que de deux sommets voisins l’un de l’autre. Propriété 1.2.9. Soit un arbre G “ pB, R, Eq tel que ΦpGq “ B Y R. Soit X “ tx P V |δGpxq ą 2u. Gc est une arborescence (respectivement une anti-arborescence) si et seulement si X X R “ H (respectivement X X B “ H). Démonstration. Il existe un arc entre deux composantes dans Gc si et seulement si il existe une arête dans G du sommet de B de la première composante au sommet de R de la deuxième. Donc le degré d’un sommet de R est le nombre d’arcs incidents intérieurement à la composante dans Gc auquel est additionné 1 pour l’arête entre les deux sommets de la composante. Si Gc est une arborescence alors il existe exactement un arc incident intérieurement à chaque composante, sauf pour la composante racine. Donc les sommets de R sont de degré 1 ou 2 et X X R “ H. Supposons que Gc ne soit pas une arborescence mais que X XR “ H. Comme Gc n’est 26 pas une arborescence, il existe au moins deux composantes sans prédécesseurs donc, comme Gc est connexe, il existe une composante avec au moins deux arcs incidents intérieurement. Donc il existe un sommet de R de degré au moins 3. Contradiction. La preuve est identique pour le cas où Gc est une anti-arborescence. 

d-extensibles de stables

Cette section donne les définitions utilisées dans le chapitre 3. Elles sont rappelées dans le chapitre. Soit un graphe G “ pV, Eq. Soit U Ă V . Un stable S Ă U de G est dit extensible par rapport à U si il existe Sp Ă pV ´Uq tel que S YSp est un stable de cardinal maximal de G. Soit un entier d tel que 1 ď d ă αpGq. Un ensemble F Ă V est un d-extensible de G si tout stable S de GrFs de cardinal d est extensible par rapport à F. On s’intéresse au problème EXTENSIBLE suivant : — Instance : Un graphe G “ pV, Eq, un entier positif 1 ď d ď αpGq, un entier positif k ď |V | — Question : Est-ce que G contient un d-extensible F de taille k ou plus ? 1.4 d-bloqueurs Cette section donne les définitions du chapitre 4. Soit Π un problème d’optimisation combinatoire défini sur un ensemble fini M=(m1, m2 … mn). Soit P une propriété sur cet ensemble telle que X Ă M satisfait P si et seulement si X est une solution admissible de Π. Étant donné L Ď M, on définit CL l’ensemble des sous-ensembles de L qui satisfont P. Ainsi, l’ensemble des solutions admissibles de M, c’est à dire l’ensemble des sous-ensembles de M qui satisfont P, est noté CM. On suppose que P est héréditaire, c’est-à-dire que si L Ď M satisfait P alors tout K Ď L satisfait P. Á chaque élément m de M sont associées deux valeurs positives : un coût cpmq et un poids wpmq. Le poids (respectivement le coût) d’un sous-ensemble de M est la somme des 27 poids (respectivement des coûts) des éléments de ce sous-ensemble. On note νwpCMq le poids maximum d’un élément de CM et δwpCMq le cardinal maximum d’un élément de CM de poids maximum. Autrement dit, νwpCMq “ maxtwpCj q|Cj P CMu et δwpCMq “ maxt|Cj ||Cj P CM, wpCj q “ νwpCMqu. Soit un entier 1 ď d ď νwpCMq. Un d-bloqueur de Π est un sous-ensemble B Ă M tel que, si on retire les éléments de B de V , on obtient νwpCM´Bq ď νwpCMq ´ d. On s’intéresse au problème BLOCK_Π(M, w, c, d) : — Instance : Un ensemble fini M=(m1, m2…mn), une fonction de coût c sur M, une fonction de poids w sur M, un entier d, un entier positif k ď |M|. — Est-ce qu’il existe un d-bloqueur B Ď M tel que |B| ď k ?