En teoría de la complejidad y teoría de grafos , el isomorfismo de subgrafos inducido es un problema de decisión NP-completo que implica encontrar un grafo dado como un subgrafo inducido de un grafo 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 mapea los vértices de G 1 a los vértices de G 2 tales 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 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. En el isomorfismo de subgrafos, estas aristas "adicionales" en G 2 pueden estar presentes.
La complejidad del isomorfismo de subgrafos inducido separa a los grafos exteriores-planares de sus grafos serie-paralelos de generalización : se puede resolver en tiempo polinomial para grafos exteriores-planares 2-conexos , pero es NP-completo para grafos serie-paralelos 2-conexos. [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 se busca encontrar un conjunto independiente grande como un subgrafo inducido de un grafo más grande, y el problema de la camarilla máxima es un problema de isomorfismo de subgrafo inducido en el que se busca encontrar un grafo de camarilla grande como un subgrafo inducido de un grafo más grande.
Aunque el problema de isomorfismo de subgrafos inducido parece sólo ligeramente diferente del problema de isomorfismo de subgrafos, la restricción "inducida" introduce cambios lo suficientemente grandes como para que podamos observar diferencias desde un punto de vista de complejidad computacional.
Por ejemplo, el problema de isomorfismo de subgrafos es NP-completo en grafos de intervalos propios conexos y en grafos de permutación bipartitos conexos, [4] pero el problema de isomorfismo de subgrafos inducido se puede resolver en tiempo polinomial en estas dos clases. [5]
Además, el problema de isomorfismo de subárbol inducido (es decir, el problema de isomorfismo de subgrafo inducido donde G 1 está restringido a ser un árbol) se puede resolver en tiempo polinomial en gráficos de intervalo, mientras que el problema de isomorfismo de subárbol es NP-completo en gráficos de intervalo apropiados. [6]