Problema de isomorfismo de subgrafos inducido

En la teoría de la complejidad y la teoría de grafos , el isomorfismo de subgrafos inducidos es un problema de decisión NP-completo que consiste en encontrar un grafo dado como subgrafo inducido de un grafo más grande.

Formalmente, el problema toma como entrada dos grafos G ₁ =( V ₁ , E ₁ ) y G ₂ =( V ₂ , E ₂ ), donde se puede suponer que el número de vértices en V ₁ es menor o igual que el número de vértices en V ₂ . G ₁ es isomorfo a un subgrafo inducido de G ₂ si existe una función inyectiva f que mapea los vértices de G ₁ a los vértices de G ₂ de tal manera que para todos los pares de vértices x , y en V ₁ , la arista ( x , y ) está en E ₁ si y solo si la arista ( f ( x ), f ( y )) está en E ₂ . La respuesta al problema de decisión es sí si existe esta función f , y no en caso contrario.

Esto difiere del problema del isomorfismo de subgrafos, ya que la ausencia de una arista en G ₁ implica que la arista correspondiente en G ₂ también debe estar ausente. En el isomorfismo de subgrafos, estas aristas "adicionales" en G ₂ pueden estar presentes.

La complejidad del isomorfismo de subgrafos inducidos separa los grafos exteriores planares de sus grafos serie-paralelo de generalización : puede resolverse en tiempo polinomial para grafos exteriores planares 2-conexos , pero es NP-completo para grafos serie-paralelo 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 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 subgrafos inducidos en el que se busca encontrar un conjunto independiente grande como subgrafo inducido de un grafo más grande, y el problema de la camarilla máxima es un problema de isomorfismo de subgrafos inducidos en el que se busca encontrar un grafo de camarilla grande como subgrafo inducido de un grafo más grande.

Aunque el problema del isomorfismo de subgrafos inducido parece solo ligeramente diferente del problema del isomorfismo de subgrafos, la restricción "inducida" introduce cambios lo suficientemente grandes como para que podamos observar diferencias desde el punto de vista de la 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árboles inducidos (es decir, el problema de isomorfismo de subgrafos inducidos donde G ₁ está restringido a ser un árbol) se puede resolver en tiempo polinomial en grafos de intervalos, mientras que el problema de isomorfismo de subárboles es NP-completo en grafos de intervalos propios. ^{[ 6 ]}