A generált részgráf izomorfizmusának problémája

A generált részgráf izomorfizmus probléma egy NP-teljes megoldhatósági probléma a komplexitáselméletben és a gráfelméletben . A probléma az, hogy egy adott gráfot egy másik, nagyobb gráf generált részgráfjaként kell megtalálni.

A probléma leírása

Formálisan a feladat két gráfot és , ahol a csúcsok száma kisebb vagy egyenlő, mint a -ben lévő csúcsok száma . izomorf egy gráf generált részgráfjával, ha van egy f injekció , amely a gráf csúcsait a gráf csúcsára képezi le úgy, hogy a V 1 összes x , y csúcspárjára egy ( x , y ) él akkor és csak akkor van jelen az E 1 - ben , ha egy él van az E2 - ben . A döntési problémára a válasz igen, ha ez az f függvény létezik, máskülönben nem.

A probléma abban különbözik a részgráf izomorfizmus problémájától , hogy a G 1 -ben lévő él hiánya azt jelenti, hogy a megfelelő élnek G 2 -ben is hiányoznia kell. Egy részgráf izomorfizmusa alatt ezek a "extra" élek a G 2 -ben jelen lehetnek.

Számítási összetettség

A generált részgráf izomorfizmus probléma összetettsége elválasztja a külső sík gráfokat az általánosításuktól, a párhuzamos-soros gráfoktól - 2-kapcsolatos külső síkbeli gráfoknál polinomiális időben is  megoldható , de 2-kapcsolatos párhuzamos soros gráfoknál NP-teljes [1] [2] .

Különleges alkalmak

A hosszú út megtalálásának speciális esete egy hiperkocka generált részgráfjaként jól tanulmányozott, és a kígyó a dobozban feladatnak nevezik [3] . A legnagyobb független halmazprobléma egy generált részgráf izomorfizmus probléma is, amelyben egy nagy független halmazt egy nagyobb gráf generált részgráfjaként keresünk, a legnagyobb klikk probléma pedig egy generált részgráf izomorfizmus probléma, amelyben egy gráf nagy klikkje. a rendszer egy nagyobb gráf generált részgráfjaként keres.

Különbség a részgráf izomorfizmus problémájától

Bár úgy tűnik, hogy a generált részgráf izomorfizmusának problémája csak kis mértékben különbözik a részgráf izomorfizmusának problémájától, a "született" szóra való korlátozás elég nagy változásokat okoz ahhoz, hogy a számítási bonyolultság szempontjából észrevehető legyen.

Például a részgráf izomorfizmus problémája NP-teljes az összekapcsolt megfelelő intervallumgráfokon és az összekapcsolt kétrészes permutációs gráfokon [4] , de a generált részgráf izomorfizmus probléma polinomiális időben is megoldható ezen a két osztályon [5] .

Sőt, az indukált részfa izomorfizmus problémája (azaz az indukált részgráf izomorfizmus problémája, ahol a G 2 gráftípust fa határolja) polinomiális időben megoldható intervallumgráfokon, míg a részfa izomorfizmus problémája sajátértékeken NP-teljes. intervallumgráfok [6] .

Jegyzetek

  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, Villanger, 2015 .
  6. ↑ Heggernes, van't Hof, Milanič, 2013 .

Irodalom