El problema del isomorfismo a un subgrafo generado

El problema de isomorfismo de subgrafo generado es un problema de resolución NP-completo en la teoría de la complejidad y la teoría de grafos . El problema es encontrar un gráfico dado como un subgráfico generado de otro gráfico más grande.

Planteamiento del problema

Formalmente, el problema toma como entrada dos gráficos y , donde el número de vértices en es menor o igual que el número de vértices en . es isomorfo a un subgrafo generado de un grafo si hay una inyección f que mapea los vértices del grafo al vértice del grafo tal que para todos los pares de vértices x , y en V 1 , una arista ( x , y ) es presente en E 1 si y solo si un borde está presente en E2 ._ La respuesta al problema de decisión es sí si existe esta función f y no en caso contrario.

El problema difiere del problema de isomorfismo de subgrafos en que la ausencia de una arista en G 1 implica que la arista correspondiente en G 2 también debe estar ausente. Bajo un isomorfismo de subgrafo, estos bordes "extra" en G 2 pueden estar presentes.

Complejidad computacional

La complejidad del problema de isomorfismo de subgrafo generado separa los gráficos planos exteriores de su generalización, gráficos paralelos en serie  : se puede resolver en tiempo polinomial para gráficos de planos exteriores 2 conectados , pero es NP-completo para gráficos paralelos en serie 2 conectados [1] [2] .

Ocasiones especiales

El caso especial de encontrar un camino largo como un subgrafo generado de un hipercubo está bien estudiado y se llama el problema de la serpiente en una caja [3] . El problema del conjunto independiente más grande también es un problema de isomorfismo de subgrafo generado, en el que se busca un conjunto independiente grande como un subgrafo generado de un gráfico más grande, y el problema de la camarilla más grande es un problema de isomorfismo de subgrafo generado, en el que una camarilla grande de un gráfico se busca como un subgrafo generado de un grafo más grande.

Diferencia del problema de isomorfismo del subgrafo

Aunque el problema del isomorfismo en un subgrafo generado parece ser solo ligeramente diferente del problema del isomorfismo en un subgrafo, la restricción a la palabra "nacer" provoca cambios lo suficientemente grandes como para notarlo desde el punto de vista de la complejidad computacional.

Por ejemplo, el problema de isomorfismo de subgrafos es NP-completo en gráficos de intervalos propios conectados y en gráficos de permutaciones bipartitas conectadas [4] , pero el problema de isomorfismo de subgrafos generado puede resolverse en tiempo polinomial en estas dos clases [5] .

Además, el problema del isomorfismo del subárbol inducido (es decir, el problema del isomorfismo del subárbol inducido, donde el tipo de gráfico G 2 está delimitado por un árbol) se puede resolver en tiempo polinomial en gráficos de intervalo, mientras que el problema del isomorfismo del subárbol es NP-completo en valores propios. gráficos de intervalos [6] .

Notas

  1. ↑ Syslo, 1982 , p. 91–97.
  2. ↑ Johnson, 1985 , pág. 434–451.
  3. ↑ Ramanujacharyulu, Menon, 1964 , pág. 131–135.
  4. ↑ Kijima, Otachi, Saitoh, Uno, 2012 , pág. 3164–3173.
  5. ↑ Heggernes, van't Hof, Meister, Villanger, 2015 .
  6. ↑ Heggernes, van't Hof, Milanič, 2013 .

Literatura