Problème du sandwich de graphes

En théorie des graphes et en informatique, le problème du sandwich de graphes est le problème consistant à trouver un graphe qui appartient à une famille particulière de graphes et qui est "pris en sandwich" entre deux autres graphes, dont l'un doit être un sous-graphe et l'autre doit être un « supergraphe » du graphe considéré.

Les problèmes de sandwich de graphes généralisent le problème de tester si un graphe donné appartient à une famille de graphes ; ils ont attiré l'attention en raison de leurs applications et en tant que généralisation naturelle des problèmes de reconnaissance.

Énoncé du problème

Étant donné un ensemble de sommets $V$, un ensemble d'arêtes $E^1$ et un autre ensemble d'arêtes plus grand $E^2$, un graphe $G=(V,E)$ est appelé un graphe sandwich pour la paire $G^1=(V,E^1)$ et $G^2=(V,E^2)$ si $E^1\subseteq E\subseteq E^2$.

Formellement, le problème du sandwich de graphe pour la propriété Π est défini comme suit :

• instance : un ensemble de sommets $V$ et deux ensembles d'arêtes $E^1\subseteq E^2$ ;
• question : existe-t-il un graphe $G=(V,E)$ tel que $E^1\subseteq E\subseteq E^2$ et qui vérifie la propriété Π ?

Le problème de reconnaissance pour une classe de graphes qui satisfont à une propriété Π est équivalent au problème particulier du sandwich de graphes où $E^1=E^2$, c'est-à-dire qu'il n'y a pas d'arêtes facultatives.

Complexité de calcul

Le problème du sandwich de graphes est NP-complet lorsque Π a la propriété d'être un graphe cordal, un graphe de comparabilité, un graphe de permutation, un graphe biparti cordal ou un graphe à chaînesModèle:,. Il peut en revanche être résolu en temps polynomial pour les graphes divisés et les graphes à seuilModèle:,, et les graphes dans lesquels tout ensemble de cinq sommets contient au plus un chemin induit à quatre sommets. L'état de la complexité a également été déterminé pour le problème du sandwich de graphes ne contenant pas de sous-graphe de type H, pour les graphes à quatre sommets H.

Bibliographie

• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article
• Modèle:Article.
• Modèle:Article.