Problema del sándwich de grafos

En teoría de grafos e informática , el problema del grafo sándwich consiste en encontrar un grafo que pertenezca a una familia particular de grafos y que esté "intercalado" entre otros dos grafos, uno de los cuales debe ser un subgrafo y el otro un supergrafo del grafo deseado.

Los problemas de sándwich de grafos generalizan el problema de comprobar si un grafo dado pertenece a una familia de grafos, y han atraído la atención debido a sus aplicaciones y como una generalización natural de los problemas de reconocimiento. ^{[ 1 ]}

Más precisamente, dado un conjunto de vértices V , un conjunto de aristas obligatorio E ¹ y un conjunto de aristas (potencialmente) mayor E ² , un grafo G  =  ( V , E ) se denomina grafo sándwich para el par G ¹ = ( V , E ¹ ), G ² = ( V , E ² ) si E ¹ ⊆ E ⊆ E ² . El problema del grafo sándwich para la propiedad Π se define de la siguiente manera: ^{[ 2 ] [ 3 ]}       

Problema del sándwich de grafos para la propiedad Π :

Instancia: Conjunto de vértices V y conjuntos de aristas E ¹ ⊆ E ² ⊆ V × V .

Pregunta: ¿Existe un grafo G = ( V , E ) tal que E ¹ ⊆ E ⊆ E ² y G satisface la propiedad Π  ?

El problema de reconocimiento para una clase de grafos (aquellos que satisfacen una propiedad Π) es equivalente al problema particular del sándwich de grafos donde E ¹  = E ² , es decir, el conjunto de aristas opcional está vacío. 

El problema del sándwich de grafos es NP-completo cuando Π es la propiedad de ser un grafo cordal , un grafo de comparabilidad , un grafo de permutación , un grafo cordal bipartito o un grafo de cadena . ^{[ 2 ] [ 4 ]} Se puede resolver en tiempo polinomial para grafos divididos , ^{[ 2 ] [ 5 ]} grafos umbral , ^{[ 2 ] [ 5 ]} y grafos en los que cada cinco vértices contienen como máximo un camino inducido de cuatro vértices . ^{[ 6 ]} El estado de complejidad también se ha establecido para los problemas ^de sándwich de grafos H -libres para cada uno de los grafos de cuatro vértices H. ^{[ 7} ]

• Dantas, Simone; de Figueiredo, Celina MH; da Silva, Murilo VG; Teixeira, Rafael B. (2011), "Sobre el problema del sándwich de subgrafo inducido prohibido", Matemáticas Aplicadas Discretas , 159 (16): 1717– 1725, doi : 10.1016/j.dam.2010.11.010.