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î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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graph sandwich problem » (voir la liste des auteurs).

Bibliographie

• Martin Charles Golumbic et Ann N. Trenk, Tolerance Graphs, Cambridge University Press, 2004, « Chapter 4. Interval probe graphs and sandwich problems », p. 63–83.
• C. M. H. de Figueiredo, L. Faria, S. Klein et R. Sritharan, « On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs », Theoretical Computer Science, vol. 381, n^os 1-3,‎ 2007, p. 57–67 (DOI 10.1016/j.tcs.2007.04.007, MR 2347393).
• Simone Dantas, Celina M.H. de Figueiredo, Murilo V.G. da Silva et Rafael B. Teixeira, « On the forbidden induced subgraph sandwich problem », Discrete Applied Mathematics, vol. 159, n^o 16,‎ 2011, p. 1717–1725 (DOI 10.1016/j.dam.2010.11.010)
• S. Dantas, S. Klein, C.P. Mello et A. Morgana, « The graph sandwich problem for P₄-sparse graphs », Discrete Mathematics, vol. 309,‎ 2009, p. 3664–3673 (DOI 10.1016/j.disc.2008.01.014).
• Simone Dantas, Celina M.H. de Figueiredo, Frédéric Maffray et Rafael B. Teixeira, « The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem », Discrete Applied Mathematics, vol. 182,‎ 2015, p. 15–24 (DOI 10.1016/j.dam.2013.09.004)
• Martin Charles Golumbic, Haim Kaplan et Ron Shamir, « Graph sandwich problems », Journal of Algorithms, vol. 19, n^o 3,‎ 1995, p. 449-473 (lire en ligne, consulté le 14 juillet 2021).
• N.V.R. Mahadev et Uri N. Peled, « Threshold Graphs and Related Topics », Annals of Discrete Mathematics, North-Holland, vol. 57,‎ 1995, p. 19–22 (lire en ligne).