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 »[1] du graphe considéré[2].

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[2].

Énoncé du problèmeModifier

É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 calculModifier

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

Notes et référencesModifier

BibliographieModifier

  • Martin Charles Golumbic et Ann N. Trenk, Tolerance Graphs, Cambridge University Press, , « 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, nos 1-3,‎ , p. 57–67 (DOI 10.1016/j.tcs.2007.04.007, Math Reviews 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, no 16,‎ , 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 P4-sparse graphs », Discrete Mathematics, vol. 309,‎ , 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,‎ , 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, no 3,‎ , p. 449-473 (lire en ligne, consulté le ).
  • N.V.R. Mahadev et Uri N. Peled, « Threshold Graphs and Related Topics », Annals of Discrete Mathematics, North-Holland, vol. 57,‎ , p. 19–22 (lire en ligne).