Problema izomorfismului la un subgraf generat

Problema izomorfismului subgrafului generat este o problemă de solubilitate NP-completă în teoria complexității și teoria grafurilor . Problema este de a găsi un grafic dat ca subgraf generat al altui grafic mai mare.

Enunțul problemei

În mod formal, problema ia ca intrare două grafice și , unde numărul de vârfuri în este mai mic sau egal cu numărul de vârfuri în . este izomorfă la un subgraf generat al unui grafic dacă există o injecție f care mapează vârfurile graficului la vârful graficului astfel încât pentru toate perechile de vârfuri x , y din V 1 , o muchie ( x , y ) este prezent în E1 dacă și numai dacă o muchie este prezentă în E2 . Răspunsul la problema deciziei este da dacă această funcție f există și nu altfel.

Problema diferă de problema izomorfismului subgrafului prin faptul că absența unei muchii în G 1 implică faptul că muchia corespunzătoare din G 2 trebuie să fie și ea absentă. Sub un izomorfism subgraf, aceste muchii „extra” din G2 pot fi prezente .

Complexitate computațională

Complexitatea problemei izomorfismului subgrafului generat separă graficele exterioare planare de generalizarea lor, graficele paralele-seriale  - poate fi rezolvată în timp polinomial pentru graficele exterioare cu două conexiuni , dar este NP-complet pentru graficele paralele-seriale cu două conexiuni [1] [2] .

Ocazii speciale

Cazul special al găsirii unei căi lungi ca subgraf generat al unui hipercub este bine studiat și se numește problema șarpelui într-o cutie [3] . Cea mai mare problemă de mulțime independentă este, de asemenea, o problemă de izomorfism de subgraf generat, în care o mulțime independentă mare este căutată ca subgraf generat al unui graf mai mare, iar cea mai mare problemă de clică este o problemă de izomorfism de subgraf generat, în care o clică mare a unui graf este căutat ca subgraf generat al unui grafic mai mare.

Diferența față de problema izomorfismului subgrafului

Deși problema izomorfismului la un subgraf generat pare să fie doar puțin diferită de problema izomorfismului la un subgraf, restricția la cuvântul „născut” provoacă schimbări suficient de mari pentru a se observa din punct de vedere al complexității computaționale.

De exemplu, problema izomorfismului subgrafului este NP-completă pe grafice de interval propriu conectate și pe grafice de permutare bipartite conectate [4] , dar problema izomorfismului subgrafului generat poate fi rezolvată în timp polinomial pe aceste două clase [5] .

Mai mult, problema izomorfismului subarboresc indus (adică problema izomorfismului subgrafului indus, unde tipul de grafic G 2 este mărginit de un arbore) poate fi rezolvată în timp polinomial pe grafice cu intervale, în timp ce problema izomorfismului subarboresc este NP-completă pe valori proprii. grafice de intervale [6] .

Note

  1. ↑ Sysło, 1982 , p. 91–97.
  2. ↑ Johnson, 1985 , p. 434–451.
  3. ↑ Ramanujacharyulu, Menon, 1964 , p. 131–135.
  4. ↑ Kijima, Otachi, Saitoh, Uno, 2012 , p. 3164–3173.
  5. ↑ Heggernes, van't Hof, Meister, Villagenger, 2015 .
  6. ↑ Heggernes, van't Hof, Milanič, 2013 .

Literatură