Problème du sandwich de graphes

Étant donné un ensemble de sommets ${\displaystyle V}$, un ensemble d'arêtes ${\displaystyle E^{1}}$ et un autre ensemble d'arêtes plus grand ${\displaystyle E^{2}}$, un graphe ${\displaystyle G=(V,E)}$ est appelé un graphe sandwich pour la paire ${\displaystyle G^{1}=(V,E^{1})}$ et ${\displaystyle G^{2}=(V^{2},E^{2})}$ si ${\displaystyle 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 ${\displaystyle V}$ et deux ensembles d'arêtes ${\displaystyle E^{1}\subseteq E^{2}}$ ;
• question : existe-t-il un graphe ${\displaystyle G=(V,E)}$ tel que ${\displaystyle 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ù ${\displaystyle E^{1}=E^{2}}$, c'est-à-dire qu'il n'y a pas d'arêtes facultatives.

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[2] - [3]. Il peut en revanche être résolu en temps polynomial pour les graphes divisés et les graphes à seuil[2] - [4], et les graphes dans lesquels tout ensemble de cinq sommets contient au plus un chemin induit à quatre sommets[5]. 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[6].

• (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).

• 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).