Maksymalny wspólny podgraf indukowany
W teorii grafów i informatyce teoretycznej maksymalny wspólny podwykres indukowany dwóch grafów G i H to graf, który jest indukowanym podgrafem zarówno G , jak i H i ma jak najwięcej wierzchołków.
Znalezienie tego wykresu jest NP-trudne . W powiązanym problemie decyzyjnym danymi wejściowymi są dwa wykresy G i H oraz liczba k . Problem polega na tym, aby zdecydować, czy G i H mają wspólny podgraf indukowany z co najmniej k wierzchołkami. Ten problem jest NP-zupełny . Jest to uogólnienie problemu indukowanego izomorfizmu podgrafu , który powstaje, gdy k jest równe liczbie wierzchołków w mniejszym z G i H , tak że cały ten wykres musi pojawić się jako indukowany podwykres drugiego wykresu.
Opierając się na twardości wyników aproksymacji dla problemu maksymalnego zbioru niezależnego , trudno jest również przybliżyć problem maksymalnego wspólnego indukowanego podgrafu. Oznacza to, że jeśli P = NP , nie ma algorytmu aproksymacji , który w czasie wielomianowym na zawsze znajduje rozwiązanie w ramach współczynnika optymalnego dla dowolnego .
Jednym z możliwych rozwiązań tego problemu jest zbudowanie modułowego wykresu iloczynu G i H . Na tym wykresie największa klika odpowiada maksymalnemu wspólnemu indukowanemu podgrafowi G i H . Dlatego algorytmy znajdowania maksymalnych klik mogą być użyte do znalezienia maksymalnego wspólnego podgrafu indukowanego. Co więcej, zmodyfikowany algorytm maksymalnej kliki może być użyty do znalezienia maksymalnego wspólnego podgrafu spójnego .
Algorytm McSplit (wraz ze swoim wariantem McSplit↓) jest algorytmem sprawdzającym w przód , który nie wykorzystuje kodowania klik, ale wykorzystuje zwartą strukturę danych do śledzenia wierzchołków w grafie H , do których każdy wierzchołek w grafie G może być odwzorowany. Obie wersje algorytmu McSplit przewyższają kodowanie kliki dla wielu klas grafów.
Algorytmy maksymalnego wspólnego indukowanego podgrafu mają długą tradycję w cheminformatyce i mapowaniu farmakoforów .