En teoría de grafos y ciencias de la computación , el problema del emparedado de gráficos es un problema de encontrar un gráfico que pertenezca a una familia particular de gráficos y que esté "emparedado" entre otros dos gráficos, uno de los cuales debe ser un subgráfico y el otro debe ser un supergrafo del grafo deseado.
Los problemas de sándwich de gráficos generalizan el problema de probar si un gráfico dado pertenece a una familia de gráficos y han llamado 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 1 y un conjunto de aristas más grande E 2 , un gráfico G = ( V , E ) se denomina gráfico sándwich para el par G 1 = ( V , E 1 ) , GRAMO 2 = ( V , mi 2 ) si mi 1 ⊆ mi ⊆ mi 2 . El problema del sándwich gráfico para la propiedad Π se define de la siguiente manera: [2] [3]
El problema de reconocimiento para una clase de grafos (aquellos que satisfacen una propiedad Π) es equivalente al problema particular del emparedado de grafos donde E 1 = E 2 , es decir, el conjunto de aristas opcional está vacío.
El problema del emparedado de grafos es NP-completo cuando Π tiene la propiedad de ser un grafo cordal , un grafo de comparabilidad, un grafo de permutación , un grafo cordal bipartito o un grafo de cadenas . [2] [4] Puede resolverse en tiempo polinomial para gráficos divididos , [2] [5] gráficos de umbral , [2] [5] y gráficos 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 resuelto para el HProblemas tipo sándwich de gráficos libres para cada uno de los gráficos de cuatro vértices H . [7]