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 gráfico dado como un subgrafo inducido de un gráfico más grande.
Formalmente, el problema toma como entrada dos gráficos 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 2 de manera que para todos los pares de vértices x , y en V 1 , 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 esta función f existe, y no en caso contrario.
Esto es diferente 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. En el isomorfismo de subgrafos, estos bordes "adicionales" en G 2 pueden estar presentes.
La complejidad del isomorfismo de subgrafos inducido separa los gráficos planos externos de sus gráficos en serie-paralelos de generalización : puede resolverse en tiempo polinomial para gráficos planos externos de 2 conexos , pero es NP-completo para gráficos en serie-paralelos de 2 conexos. [1] [2]
El caso especial de encontrar un camino largo como subgrafo inducido de un hipercubo ha sido particularmente bien estudiado y se denomina problema de la serpiente en la caja . [3] El problema de conjunto máximo independiente 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 gráfico más grande, y el problema de camarilla máxima es un problema de isomorfismo de subgrafo inducido en el que se busca Encuentre un gráfico de camarilla grande como un subgrafo inducido de un gráfico más grande.
Aunque el problema del isomorfismo de subgrafos inducido parece sólo ligeramente diferente del problema del isomorfismo de subgrafos, la restricción "inducida" introduce cambios lo suficientemente grandes como para que podamos presenciar diferencias 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 permutación bipartitos conectados, [4] pero el problema de isomorfismo de subgrafos inducido se puede resolver en tiempo polinómico 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 adecuados. [6]