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 »G est un supergraphe de H si H est un sou-graphe de G 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 , un ensemble d'arêtes et un autre ensemble d'arêtes plus grand , un graphe est appelé un graphe sandwich pour la paire et si .
Formellement, le problème du sandwich de graphe pour la propriété Π est défini comme suit : instance : un ensemble de sommets et deux ensembles d'arêtes ; question : existe-t-il un graphe tel que 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ù , 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înes.. Il peut en revanche être résolu en temps polynomial pour les graphes divisés et les graphes à seuil., 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..
Notes et références
Bibliographie . .
.
. .
Catégorie:Théorie des graphes