En teoría de grafos e informática , el problema del gráfico sándwich es un problema de encontrar un gráfico que pertenezca a una familia particular de gráficos y que esté "intercalado" entre otros dos gráficos, uno de los cuales debe ser un subgrafo y el otro debe ser un supergrafo del gráfico deseado.
Los problemas de gráficos sándwich generalizan el problema de probar si un gráfico determinado pertenece a una familia de gráficos y han atraído la atención por sus aplicaciones y como una generalización natural de los problemas de reconocimiento. [1]
Declaración del problema
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 de gráfico sándwich para la propiedad Π se define de la siguiente manera: [2] [3]
- Problema de sándwich gráfico para la propiedad Π :
- Instancia: Conjunto de vértices V y conjuntos de aristas E 1 ⊆ E 2 ⊆ V × V .
- Pregunta: ¿Existe una gráfica G = ( V , E ) tal que E 1 ⊆ E ⊆ E 2 y G satisfaga la propiedad Π?
El problema de reconocimiento para una clase de gráficos (aquellos que satisfacen una propiedad Π) es equivalente al problema de gráfico sándwich particular donde E 1 = E 2 , es decir, el conjunto de aristas opcional está vacío.
Complejidad computacional
El problema del gráfico sándwich es NP-completo cuando Π tiene la propiedad de ser un gráfico cordal , un gráfico de comparabilidad , un gráfico de permutación , un gráfico bipartito cordal o un gráfico de cadena . [2] [4] Se puede resolver 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 una ruta inducida de cuatro vértices . [6]
El estado de complejidad también se ha resuelto para los problemas de sándwich de gráficos libres de H para cada uno de los gráficos de cuatro vértices H. [7]
Referencias
- ^ Golumbic, Martín Charles; Trenk, Ann N. (2004), "Capítulo 4. Gráficos de sonda de intervalo y problemas sándwich", Gráficos de tolerancia , Cambridge, págs..
- ^ abcd Golumbic, Martín Charles; Kaplan, Haim; Shamir, Ron (1995), "Problemas de sándwich de gráficos", J. Algoritmos , 19 : 449–473, doi : 10.1006/jagm.1995.1047.
- ^ Golumbic, Martin Charles (2004), Teoría de grafos algorítmicos y gráficos perfectos, Annals of Discrete Mathematics, vol. 57 (2ª ed.), Elsevier, pág. 279.
- ^ de Figueiredo, CMH; Faria, L.; Klein, S.; Sritharan, R. (2007), "Sobre la complejidad de los problemas sándwich para gráficos fuertemente cordales y gráficos bipartitos cordales", Theoretical Computer Science , 381 (1–3): 57–67, doi : 10.1016/j.tcs.2007.04 .007 , SEÑOR 2347393.
- ^ ab Mahadev, NVR; Peled, Uri N. (1995), Gráficos de umbrales y temas relacionados, Annals of Discrete Mathematics, vol. 57, Holanda Septentrional, págs. 19-22.
- ^ Dantas, S.; Klein, S.; Mello, CP; Morgana, A. (2009), "El problema del gráfico sándwich para gráficos dispersos P 4 ", Matemáticas discretas , 309 : 3664–3673, doi : 10.1016/j.disc.2008.01.014.
- ^ Dantas, Simone; de Figueiredo, Celina MH; Maffray, Frédéric; Teixeira, Rafael B. (2013), "La complejidad de los problemas de sándwich de subgrafo prohibido y el problema de sándwich de partición sesgada", Matemáticas aplicadas discretas : disponible en línea el 11 de octubre de 2013, doi : 10.1016/j.dam.2013.09.004.
Lectura adicional
- 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 : 1717–1725, doi : 10.1016/j.dam.2010.11.010.
