Problema de isomorfismo de subgrafo inducido
En la teoría de la complejidad y la teoría de grafos , el isomorfismo de subgrafo inducido es un problema de decisión NP-completo que implica encontrar un gráfico dado como un subgrafo inducido de un gráfico más grande.
Formalmente, el problema toma como entrada dos grafos G 1 =( V 1 , E 1 ) y G 2 =( V 2 , E 2 ), donde se puede suponer que el número de vértices en V 1 es menor o igual que el número de vértices en V 2 . G 1 es isomorfo a un subgrafo inducido de G 2 si hay una función inyectiva f que asigna los vértices de G 1 a los vértices de G 2tal que para todos los pares de vértices x , y en V 1 , la arista ( x , y ) está en E 1 si y solo si la arista ( f ( x ), f ( y )) está en E 2 . La respuesta al problema de decisión es sí si existe esta función f y no en caso contrario.
Esto es diferente del problema del isomorfismo del subgrafo en que la ausencia de un borde en G 1 implica que el borde correspondiente en G 2 también debe estar ausente. En el isomorfismo de subgrafos, estos bordes "extra" en G 2 pueden estar presentes.
La complejidad del isomorfismo de subgrafo inducido separa los gráficos planos exteriores de sus gráficos serie-paralelo de generalización : puede resolverse en tiempo polinomial para gráficos planos exteriores 2 conectados , pero es NP-completo para gráficos serie paralelo 2 conectados. [1] [2]
El caso especial de encontrar un camino largo como un subgrafo inducido de un hipercubo ha sido particularmente bien estudiado y se llama el problema de la serpiente en la caja . [3] El problema del conjunto independiente máximo es también un problema de isomorfismo de subgrafo inducido en el que uno busca encontrar un conjunto independiente grande como un subgrafo inducido de un gráfico más grande, y el problema de la camarilla máxima es un problema de isomorfismo de subgrafo inducido en el que uno busca encuentre un gráfico de camarilla grande como un subgráfico inducido de un gráfico más grande.
Aunque el problema de isomorfismo de subgrafo inducido parece solo ligeramente diferente del problema de isomorfismo de subgrafo, la restricción "inducida" introduce cambios lo suficientemente grandes como para que podamos observar diferencias desde el punto de vista de la complejidad computacional.
