Graphe à distance héréditaire
En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier.
Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977[1], alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs[2] qui ont montré que ce sont des graphes parfaits[3].
Les graphes à distance héréditaire constituent une classe de graphes d'intersection[4] ; un modèle d'intersection a été donné par Gioan et Paul en 2012[5].
Définition et caractérisation
modifierLa définition originale d'un graphe à distance héréditaire est la suivante : c'est un graphe G tel que, pour deux sommets u et v appartenant à un sous-graphe induit connexe H de G, un plus court chemin reliant u et v dans G est contenu dans H, de sorte que la distance entre u et v dans H est la même que la distance dans G.
Les graphes à distance héréditaire peuvent être caractérisés de plusieurs autres manières équivalentes[6] :
- Ce sont les graphes dans lesquels tout chemin induit est un chemin le plus court, ou de manière équivalente les graphes dans lesquels tout chemin qui n'est pas de longueur minimale a au moins une arête reliant deux sommets non consécutifs du chemin.
- Ce sont les graphes dans lesquels chaque cycle de longueur ≥ 5 a au moins deux diagonales qui se croisent.
- Ce sont les graphes dans lesquels, pour quatre sommets quelconques, deux au moins des trois sommes de distances , et sont égales.
- Ce sont les graphes qui n'ont pas de sous-graphe isométrique qui est un cycle de longueur ≥ 5, ou l'un des trois graphes suivants : un cycle à 5 sommets avec une corde, un cycle à 5 sommets avec deux cordes qui ne se croisent pas, et un cycle à 6 sommets avec une corde reliant des sommets opposés.
- Ce sont les graphes qui peuvent être construits à partir d'un seul sommet par une séquence des trois opérations suivantes, montrées sur l'illustration :
- Adjonction d'un nouveau sommet pendant connecté à un sommet existant du graphe.
- Remplacement d'un sommet du graphe par une paire de sommets, dont chacun a le même ensemble de voisins que le sommet remplacé. Les nouveaux sommets sont appelés faux jumeaux.
- Remplacement d'un sommet du graphe par une paire de sommets, dont chacun a le même ensemble de voisins que le sommet remplacé, et en plus est relié à l'autre sommet de la paire. Les nouveaux sommets sont appelés vrais jumeaux.
- Ce sont les graphes qui peuvent être complètement décomposés en cliques et en étoiles (les graphes bipartis complets ) par une décomposition scindée. Une telle décomposition commence par une partition du graphe en deux sous-ensembles, telle que les arêtes séparant les deux sous-ensembles forment un sous-graphe biparti complet, puis forme deux graphes plus petits en remplaçant chacun des deux côtés de la partition par un seul sommet, et récursivement partitionne ces deux sous-graphes[7].
- Ce sont les graphes qui ont une largeur de rang égale à un, où la largeur de rang d'un graphe est définie comme le minimum, sur toutes les partitions hiérarchiques des sommets du graphe, du rang maximum parmi certaines sous-matrices de la matrice d'adjacence du graphe déterminée par la partition[8].
- Ce sont les graphes dits « sans HHDG », caractérisés par graphes interdits, à savoir sans sous-graphe induit qui est une « maison » (le graphe complémentaire d'un graphe chemin à cinq sommets), un « trou » (un cycle de cinq sommets ou plus), un « domino » (cycle à six sommets plus une arête diagonale entre deux sommets opposés) ou un « graphe gemme » (cycle à cinq sommets plus deux diagonales incidentes au même sommet).
Relation avec d'autres familles de graphes
modifierTout graphe à distance héréditaire est un graphe parfait[9], plus précisément un graphe parfaitement ordonnable (en)[10] et un graphe de Meyniel (en). Chaque graphe à distance héréditaire est également un graphe de parité (en), c'est-à-dire un graphe dans lequel deux chemins quelconques induits entre une même paire de sommets ont une longueur de même parité[11]. Toute puissance paire d'un graphe à distance héréditaire G (c'est-à-dire le graphe G 2 i formé en connectant des paires de sommets à une distance d'au plus 2 i dans G) est un graphe cordal[12].
Tout graphe à distance héréditaire peut être représenté comme le graphe d'intersection des cordes d'un cercle, formant un graphe cercle (en). Cette propriété peut se vérifier au fur et à mesure lors de la construction du graphe par adjonction des sommets pendants, des faux jumeaux et des vrais jumeaux, en construisant à chaque étape un ensemble correspondant de cordes représentant le graphe : l'adjonction d'un sommet pendant correspond à l'ajout d'une corde à proximité des extrémités d'une corde existante sans qu'il ne croise que cette corde ; l'adjonction de faux jumeaux correspond au remplacement d'une corde par deux cordes parallèles croisant le même ensemble d'autres cordes ; et l'adjonction de vrais jumeaux correspond au remplacement d'une corde par deux cordes qui se croisent mais sont presque parallèles et croisent le même ensemble d'autres cordes.
Un graphe à distance héréditaire est biparti si et seulement s'il est sans triangle. Des graphes bipartis à distance héréditaire peuvent être construits à partir d'un seul sommet en ajoutant uniquement des sommets pendants et des faux jumeaux, puisque de vrais jumeaux formeraient un triangle, alors que l'adjonction de sommets pendants et de faux jumeaux préserve la bipartité. Chaque graphe biparti à distance héréditaire est biparti cordal (en) et modulaire (en)[13].
Les graphes qui peuvent être construits à partir d'un sommet par sommets pendants et vrais jumeaux et sans opération de faux jumeaux, sont des cas particuliers des graphes ptolémaïques et incluent les graphes de blocs. Les graphes qui peuvent être construits à partir d'un sommet par des opérations de faux jumeaux et de vrais jumeaux, sans ajout de sommet pendant, sont les cographes, qui sont donc des graphes à distance héréditaire ; les cographes sont exactement les unions disjointes des graphes à distance héréditaire de diamètre 2. Le voisinage de tout sommet dans un graphe à distance héréditaire est un cographe. La fermeture transitive du graphe orienté obtenu en choisissant une orientation arbitraire des arêtes d'un arbre est toujours à distance héréditaire ; le cas particulier où l'arbre est orienté de manière cohérente en partant d'un sommet forme une sous-classe de graphes à distance héréditaire connue sous le nom de graphes trivialement parfaits ; ils sont aussi appelés cographes cordaux[14].
Algorithmes
modifierLes graphes à distance héréditaire peuvent être reconnus et traduits en temps linéaire en une séquence de sommets pendants et d'opérations jumelles[15].
Les graphes à distance héréditaire étant parfaits, certains problèmes d'optimisation peuvent être résolus en temps polynomial dans ce cas bien qu'ils soient NP-difficiles pour des classes de graphes plus générales. Ainsi, il est possible de trouver en temps polynomial la clique maximale ou le stable maximal dans un graphe à distance héréditaire, ou de trouver une coloration optimale d'un graphe à distance héréditaire. Ainsi, Cogis et Thierry[16] présentent un algorithme direct simple pour les stables pondérés maximaux dans les graphes à distance héréditaire, basé sur la décomposition du graphe en sommets pendants et sommets jumeaux (corrigeant par là-même une première tentative de (Hammer et Maffray 1990)). Comme les graphes à distance héréditaire sont parfaitement ordonnables, ils peuvent être colorés de manière optimale en temps linéaire en utilisant un parcours LexBFS qui fournit un ordre parfait, suivi d'une coloration gloutonne.
Les graphes à distance héréditaire étant des graphes circulaires, ils héritent des algorithmes en temps polynomial pour les graphes circulaires ; par exemple, il est possible de déterminer en temps polynomial la largeur arborescente de tout graphe circulaire et donc de tout graphe à distance héréditaire[17]. De plus, la largeur de clique de tout graphe à distance héréditaire est au plus égale à trois[18]. En conséquence, et par le théorème de Courcelle, des algorithmes de programmation dynamique efficaces existent pour de nombreux problèmes sur ces graphes[19].
Plusieurs autres problèmes d'optimisation peuvent également être résolus plus efficacement en utilisant des algorithmes spécialement conçus pour les graphes à distance héréditaire. Comme l'ont montré D'Atri et Moscarini en 1988[20], un ensemble dominant connexe minimum (ou de manière équivalente un arbre couvrant avec un nombre maximum de feuilles) peut être déterminé en temps polynomial pour un graphe à distance héréditaire. Un cycle hamiltonien ou un chemin hamiltonien peut également être trouvé en temps polynomial dans tout graphe à distance héréditaire[21].
Notes et références
modifier- Howorka (1997).
- Olaru et Sachs (1970).
- Olaru et Sachs ont montré que les graphes où tout cycle de longueur ≥ 5 a plus d'une paire de diagonales qui se croisent sont α-parfaits (Olaru Sachs (1970), théorème 5). Par Lovász (1972), la α-perfection est une formulation équivalente de la définition de graphes parfaits.
- McKee et McMorris (1999).
- Gioan et Paul (2012).
- Howorka 1977; Bandelt et Mulder 1986; Hammer et Maffray 1990; Brandstädt, Le et Spinrad 1999, Theorem 10.1.1, p. 147.
- Gioan et Paul (2012). Une décomposition similaire a été utilisée pour le tracé de graphes par Eppstein, Goodrich et Meng (2006) et pour les graphes biparti à distance héréditaire par Hui, Schaefer et Štefankovič (2004).
- Oum (2005).
- Howorka (1977).
- Brandstädt, Le et Spinrad 1999, pp. 70–71 et 82.
- Brandstädt, Le et Spinrad 1999, p. 45.
- Brandstädt, Le et Spinrad 1999, Theorem 10.6.14, p. 164.
- Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions.
- Cornelsen et Di Stefano (2005).
- (Damiand, Habib et Paul 2001) ; (Gioan et Paul 2012). Une borne linéaire donnée antérieurement dans (Hammer et Maffray 1990) est erronée, comme l'a observé Damiand.
- Cogis et Thierry (2005).
- Kloks (1996); (Brandstädt, Le et Spinrad 1999), p. 170.
- Golumbic et Rotics (2000).
- Courcelle, Makowski et Rotics 2000; Espelage, Gurski et Wanke 2001.
- D'Atri et Moscarini (1988).
- Hsieh et al. 2002 ; Müller et Nicolai 1993.
Bibliographie
modifier- Hans-Jürgen Bandelt et Henry Martyn Mulder, « Distance-hereditary graphs », Journal of Combinatorial Theory, Series B, vol. 41, no 2, , p. 182–208 (DOI 10.1016/0095-8956(86)90043-2
, MR 0859310). - Andreas Brandstädt, Van Bang Le et Jeremy Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, (ISBN 0-89871-432-X, lire en ligne
). - Olivier Cogis et Éric Thierry, « Computing maximum stable sets for distance-hereditary graphs », Discrete Optimization, vol. 2, no 2, , p. 185–188 (DOI 10.1016/j.disopt.2005.03.004 , MR 2155518).
- Sabine Cornelsen et Gabriele Di Stefano, « Treelike comparability graphs: characterization, recognition, and applications », Lecture Notes in Computer Science, Springer-Verlag, vol. 3353 « Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004) », , p. 46–57 (DOI 10.1007/978-3-540-30559-0_4, MR 2158633), (ISBN 9783540241324 et 9783540305590).
- Bruno Courcelle, Johann A. Makowski et Udi Rotics, « Linear time solvable optimization problems on graphs on bounded clique width », Theory of Computing Systems, vol. 33, no 2, , p. 125–150 (DOI 10.1007/s002249910009).
- Alessandro D'Atri et Marina Moscarini, « Distance-hereditary graphs, Steiner trees, and connected domination », SIAM Journal on Computing, vol. 17, no 3, , p. 521–538 (DOI 10.1137/0217032, MR 0941943).
- Guillaume Damiand, Michel Habib et Christophe Paul, « A simple paradigm for graph recognition: application to cographs and distance hereditary graphs », Theoretical Computer Science, vol. 263, nos 1–2, , p. 99–111 (DOI 10.1016/S0304-3975(00)00234-6, MR 1846920, lire en ligne).
- David Eppstein, Michael T. Goodrich et Jeremy Yu Meng, « Delta-confluent drawings », Lecture Notes in Computer Science, Springer-Verlag, vol. 3843 « Proc. 13th Int. Symp. Graph Drawing (GD 2005) », , p. 165–176 (DOI 10.1007/11618058_16, MR 2244510, arXiv cs.CG/0510024).
- Wolfgang Espelage, Frank Gurski et Egon Wanke, « How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time », Lecture Notes in Computer Science, Springer-Verlag, vol. 2204 « Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001) », , p. 117–128.
- Emeric Gioan et Christophe Paul, « Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs », Discrete Applied Mathematics, vol. 160, no 6, , p. 708–733 (DOI 10.1016/j.dam.2011.05.007, arXiv 0810.1823).
- Martin Charles Golumbic et Udi Rotics, « On the clique-width of some perfect graph classes », International Journal of Foundations of Computer Science, vol. 11, no 3, , p. 423–443 (DOI 10.1142/S0129054100000260, MR 1792124).
- Peter Ladislaw Hammer et Frédéric Maffray, « Completely separable graphs », Discrete Applied Mathematics, vol. 27, nos 1–2, , p. 85–99 (DOI 10.1016/0166-218X(90)90131-U , MR 1055593).
- Edward Howorka, « A characterization of distance-hereditary graphs », The Quarterly Journal of Mathematics, Second Series, vol. 28, no 112, , p. 417–420 (DOI 10.1093/qmath/28.4.417, MR 0485544).
- Sun-yuan Hsieh, Chin-wen Ho, Tsan-sheng Hsu et Ming-tat Ko, « Efficient algorithms for the Hamiltonian problem on distance-hereditary graphs », Lecture Notes in Computer Science, Springer-Verlag, vol. 2387 « Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings », , p. 51–75 (ISBN 978-3-540-43996-7, DOI 10.1007/3-540-45655-4_10, MR 2064504).
- Peter Hui, Marcus Schaefer et Daniel Štefankovič, « Train tracks and confluent drawings », Lecture Notes in Computer Science, Springer-Verlag, vol. 3383 « Proc. 12th Int. Symp. Graph Drawing (GD 2004) », , p. 318–328.
- Ton Kloks, « Treewidth of circle graphs », International Journal of Foundations of Computer Science, vol. 7, no 2, , p. 111–120 (DOI 10.1142/S0129054196000099).
- László Lovász, « Normal hypergraphs and the perfect graph conjecture », Discrete Mathematics, vol. 2, no 3, , p. 253–267 (DOI 10.1016/0012-365X(72)90006-4 , MR 0302480).
- Terry A. McKee et Frederick R. McMorris, Topics in Intersection Graph Theory, Philadelphia, Society for Industrial and Applied Mathematics, coll. « SIAM Monographs on Discrete Mathematics and Applications » (no 2), (ISBN 0-89871-430-3, DOI 10.1137/1.9780898719802, MR 1672910)
- Haiko Müller et Falk Nicolai, « Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs », Information Processing Letters, vol. 46, no 5, , p. 225–230 (DOI 10.1016/0020-0190(93)90100-N, MR 1228792).
- Sang-il Oum, « Rank-width and vertex-minors », Journal of Combinatorial Theory Series B, vol. 95, no 1, , p. 79–100 (DOI 10.1016/j.jctb.2005.03.003 , MR 2156341).
- Horst Sachs, « On the Berge conjecture concerning perfect graphs », dans Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, (MR 0272668), p. 377–384.
Liens externes
modifier- « Distance-hereditary graphs », Information System on Graph Classes and their Inclusions, sur graphclasses.org.
