Graphe à distance héréditaire

La 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 ${\displaystyle u,v,w,x}$ quelconques, deux au moins des trois sommes de distances ${\displaystyle d(u,v)+d(w,x)}$, ${\displaystyle d(u,w)+d(v,x)}$ et ${\displaystyle d(u,x)+d(v,w)}$ 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.

Les trois opérations qui permettent de construire tout graphe distance-héréditaire.

• 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 :
  1. Adjonction d'un nouveau sommet pendant connecté un sommet existant du graphe.
  2. 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.
  3. 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 ${\displaystyle K_{1,q}}$ ) 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 bipartite 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).

Tout 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].

Les 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].

• « Distance-hereditary graphs », Information System on Graph Classes and their Inclusions, sur http://www.graphclasses.org/index.html.