Problem izomorfizmu podgrafu indukowanego
W teorii złożoności i teorii grafów indukowany izomorfizm podgrafu jest NP-zupełnym problemem decyzyjnym , który polega na znalezieniu danego grafu jako indukowanego podgrafu większego grafu.
Oświadczenie o problemie
Formalnie problem przyjmuje jako dane wejściowe dwa grafy G 1 =( V 1 , E 1 ) i G 2 = ( V 2 , E 2 ), gdzie można przyjąć, że liczba wierzchołków w V 1 jest mniejsza lub równa liczba wierzchołków w V 2 . G 1 jest izomorficzny z indukowanym podgrafem G 2 , jeśli istnieje funkcja iniekcyjna f który odwzorowuje wierzchołki G 1 na wierzchołki G 2 w taki sposób, że dla wszystkich par wierzchołków x , y w V 1 , krawędź ( x , y ) jest w E 1 wtedy i tylko wtedy, gdy krawędź ( f ( x ), f ( y )) jest w E 2 . Odpowiedź na problem decyzyjny brzmi: tak, jeśli ta funkcja f istnieje, a nie w przeciwnym razie.
Różni się to od problemu izomorfizmu podgrafu tym, że brak krawędzi w G 1 implikuje, że odpowiednia krawędź w G 2 również musi być nieobecna. W izomorfizmie podgrafu te „dodatkowe” krawędzie w G 2 mogą być obecne.
Złożoność obliczeniowa
Złożoność indukowanego izomorfizmu podgrafu oddziela grafy płaszczyzny zewnętrznej od ich grafów równoległych szeregów uogólnienia : można ją rozwiązać w czasie wielomianowym dla grafów płaszczyzn zewnętrznych 2-połączonych , ale jest NP-zupełna dla grafów 2-połączonych serii-równoległych.
Przypadki specjalne
Szczególny przypadek znalezienia długiej ścieżki jako indukowanego podwykresu hipersześcianu został szczególnie dobrze zbadany i jest nazywany problemem węża w pudełku . Problem maksymalnego zbioru niezależnego jest również problemem indukowanego izomorfizmu podgrafu, w którym dąży się do znalezienia dużego niezależnego zbioru jako indukowanego podgrafu większego grafu, a problem maksymalnej kliki jest problemem indukowanego izomorfizmu podgrafu, w którym dąży się do znalezienia dużego wykres kliki jako indukowany podgraf większego grafu.
Różnice z problemem izomorfizmu podgrafu
Chociaż problem indukowanego izomorfizmu podgrafu wydaje się tylko nieznacznie różnić od problemu izomorfizmu podgrafu, „indukowane” ograniczenie wprowadza zmiany na tyle duże, że możemy być świadkami różnic z punktu widzenia złożoności obliczeniowej.
Na przykład problem izomorfizmu podgrafu jest NP-zupełny na połączonych grafach odpowiednich przedziałów i na połączonych dwudzielnych grafach permutacji, ale problem izomorfizmu indukowanego podgrafu można rozwiązać w czasie wielomianowym na tych dwóch klasach.
Ponadto problem indukowanego izomorfizmu poddrzewa (tj. problem izomorfizmu indukowanego podgrafu, w którym G 1 jest ograniczony do drzewa) można rozwiązać w czasie wielomianowym na grafach interwałowych, podczas gdy problem izomorfizmu poddrzewa jest NP-zupełny na odpowiednich grafach interwałowych.