graph isomorphism problem

graph isomorphism problem (tsz. graph isomorphism problems)

1. (informatika) A probléma a következőképpen fogalmazható meg:

Adott két egyszerű, nem irányított gráf, ${\textstyle G=(V_{G},E_{G})}$ és ${\textstyle H=(V_{H},E_{H})}$. Meg kell határozni, létezik-e bijekció

$${\displaystyle f:V_{G}\;\longrightarrow \;V_{H}}$$ olyan módon, hogy $${\displaystyle \{u,v\}\in E_{G}\quad \Longleftrightarrow \quad \{f(u),f(v)\}\in E_{H}.}$$

Ha igen, akkor azt mondjuk, hogy ${\textstyle G}$ és ${\textstyle H}$ izomorfok.

• Kimeneti jelleg: A probléma döntési verziója („van-e izomorfizmus?”) NP-ben van, de nem ismerjük, NP-teljes-e.

• Komplexitási osztály: A Graph Isomorphism (GI) az egyik ritka probléma, ami NP-ben van, de nem tudjuk, hogy NP-teljes-e, sőt a legújabb eredmények szerint valószínűleg különbözik mind a P-től, mind az NP-teljestől.

• Legújabb eredmények: 2015-ben Babai László kijelentette, hogy egy kvázi-polinomiális algoritmust talált GI-re, azaz futási ideje

  $${\displaystyle \exp {\bigl (}(\log n)^{O(1)}{\bigr )},}$$

  mely lényegesen jobb, mint a korábbi szuperpolinomiális-szintű eljárások.

1. Bruteforce keresés

   $${\displaystyle O(n!\times \mathrm {check} (n))}$$

   összes permutációt kipróbálva, ahol ${\textstyle \mathrm {check} (n)}$ az él-illeszkedés ellenőrzés költsége (${\textstyle O(n^{2})}$). Ez persze teljesen használhatatlan nagy ${\textstyle n}$-re.

2. Weisfeiler–Lehman finomítás Iteratív színező-eljárás: a csúcsokat kezdetben fokszámuk szerinti színnel látjuk el, majd lépésről lépésre a szomszédok színeinek multiszetjét beépítve finomítunk. Ha két gráf különböző színeloszlást kap, nem izomorf. Ez hatékony heuristikaként szolgál számos esetre, de vannak konstruált kivételek (ambiguitások).

3. Divide and conquer és csoportelmélet A gráf automorfizmus-csoportjának struktúráját használva a permutációs csoportok dekompozíciójára és visszafejtésére épülnek a Babai-féle kvázi-polinomiális algoritmusok.

• Fák: A gyökér nélküli fa izomorfizmusát lineáris időben eldönthetjük, például AHU-algoritmussal (Aho–Hopcroft–Ullman).
• Planáris gráfok: Lineáris vagy ${\textstyle O(n\log n)}$ algoritmusok léteznek (Hopcroft–Wong).
• Forgatókönyv-korlátos gráfok: Ha a gráf kis kiegyenlítő (treewidth), clique-width stb. közel van, dinamikus programozással polinomiális idő alatt.
• Régiók szerint rendezett gráfok (például intervallumgráfok, chordális gráfok): polinomiális algoritmusok.

• NP: Könnyen ellenőrizhető egy adott bijekció, hogy valóban él-illeszkedést tart-e, így a döntési verzió NP-ben van.
• NP-teljesség nyitott: Nem tudjuk, hogy GI-nek van-e NP-teljes státusza. A legtöbb szakértő két fő lehetőség egyikét valószínűbb:
  1. GI ∉ P, GI ∉ NP-complete (intermediális probléma).
  2. GI ∈ P — Babai eredménye kvázi-polinomiális közelítés, esetleg tovább javítható.
• Közeli redukciók: GI több problémával kapcsolatban intermediális állapotot tölt be, például az Graph Automorphism (a gráf saját szimmetriáinak megtalálása) ugyancsak rejtély.

1. Kémiai informatikai molekuláris párosítás Molekulamodellek izomorf izomerjeinek felismerése (képletek gráf-formában).
2. Szociális háló-analízis Struktúra-egyezés két hálózat között, anomáliák, minták keresése.
3. Számítógépes látás és mintázatfelismerés Grafikusként ábrázolt objektumok párosítása, forgatás-transzláció invariancia.
4. Hardver-verifikáció Áramköri gráfok izomorfizmusának ellenőrzése logikai hálózatok hasonlóságára.

• Permutációs „űr”: Az ${\textstyle n}$ csúcsú gráfnál ${\textstyle n!}$ lehetséges képfunkció.
• Szimmetria és automorfizmusok: Egyes gráfok nagyon nagy automorfizmus-csoporttal rendelkeznek (pl. teljes gráf, kör), ami nehezíti a distinktív struktúra megtalálását.
• Konstrukciós ellenpéldák: Léteznek konstruált gráfcsaládok, amelyekkel a WL-eljárás több lépés után is sikertelen („cospectral” gráfok).

A Graph Isomorphism Problem egy olyan „intermediális” komplexitású feladat, amely nem sorolódik ismerten sem P-be, sem az NP-teljes kategóriába. A jelenleg legjobb általános algoritmus kvázi-polinomiális futási idejű, miközben számos speciális gráfosztályra lineáris vagy polinomiális eljárások léteznek. Alkalmazási területei a tudomány és az ipar több pontjáig érnek, és a probléma megoldása mély összefüggéseket tár fel a kombinatorika, a csoportelmélet és a számítógépes algoritmusok között.

• graph isomorphism problem - Szótár.net (en-hu)
• graph isomorphism problem - Sztaki (en-hu)
• graph isomorphism problem - Merriam–Webster
• graph isomorphism problem - Cambridge
• graph isomorphism problem - WordNet
• graph isomorphism problem - Яндекс (en-ru)
• graph isomorphism problem - Google (en-hu)
• graph isomorphism problem - Wikidata
• graph isomorphism problem - Wikipédia (angol)