Problém grafového izomorfismu - Graph isomorphism problem - Wikipedia

Nevyřešený problém v informatice: Může být problém izomorfismu grafu vyřešen v polynomiálním čase? (více nevyřešených problémů v informatice)

The problém grafového izomorfismu je výpočetní problém stanovení, zda dva konečné grafy jsou izomorfní.

Není známo, že by problém byl řešitelný v polynomiální čas ani být NP-kompletní, a proto mohou být výpočetní třída složitosti NP-střední. Je známo, že problém isomorfismu grafu je v nízká hierarchie z třída NP, což znamená, že není NP-úplný, pokud polynomiální časová hierarchie se zhroutí na druhou úroveň.^[1] Současně lze izomorfismus pro mnoho speciálních tříd grafů řešit v polynomiálním čase a v praxi lze izomorfismus grafů často řešit efektivně.^[2]

Tento problém je zvláštním případem problém izomorfismu podgrafu,^[3] který se ptá, zda daný graf G obsahuje podgraf, který je izomorfní s jiným daným grafem H; je známo, že tento problém je NP-úplný. Je také známo, že se jedná o zvláštní případ neabelský skrytý problém s podskupinou přes symetrická skupina.^[4]

V oblasti rozpoznávání obrazu to je známé jako přesná shoda grafu.^[5]

Nejmodernější

Nejlepší aktuálně přijímaný teoretický algoritmus je způsoben Babai & Luks (1983), a je založen na dřívější práci od Luks (1982) v kombinaci s a dílčí faktor algoritmus V. N. Zemlyachenka (Zemlyachenko, Korneenko & Tyshkevich 1985 ). Algoritmus má dobu běhu 2^{Ó(√n logn)} pro grafy s n vrcholy a spoléhá na klasifikace konečných jednoduchých skupin. Bez věta CFSG, o něco slabší vazba 2^{Ó(√n log2 n)} byl získán jako první pro silně pravidelné grafy podle László Babai  (1980 ), a poté rozšířen na obecné grafy o Babai & Luks (1983). Vylepšení exponenta √n je velkým otevřeným problémem; pro velmi pravidelné grafy to udělal Spielman (1996). Pro hypergrafy omezené pozice, a subexponenciální horní hranice odpovídající případu grafů byla získána pomocí Babai & Codenotti (2008).

V listopadu 2015 Babai oznámila kvazipolynomický čas algoritmus pro všechny grafy, tedy jeden s dobou chodu ${ displaystyle 2 ^ {O (( log n) ^ {c})}}$ pro některé pevné ${ displaystyle c> 0}$.^[6][7][8] 4. ledna 2017 Babai stáhl kvazi-polynomiální nárok a uvedl a subexponenciální čas místo toho vázáno Harald Helfgott objevil chybu v důkazu. 9. ledna 2017 Babai oznámil opravu (zveřejněna v plném rozsahu 19. ledna) a obnovil kvazi-polynomiální nárok, přičemž Helfgott opravu potvrdil.^[9][10] Helfgott dále tvrdí, že člověk může trvat C = 3, takže doba provozu je 2^{O ((log n)3)}.^[11][12] Nový důkaz ještě nebyl plně recenzován.

Existuje několik konkurenčních praktických algoritmů pro izomorfismus grafů, například ty, které jsou způsobeny McKay (1981), Schmidt & Druffel (1976), a Ullman (1976). I když se zdá, že fungují dobře náhodné grafy, hlavní nevýhodou těchto algoritmů je jejich exponenciální časový výkon v nejhorší případ.^[13]

Problém izomorfismu grafu je výpočetně ekvivalentní problému výpočtu skupina automorfismu grafu,^[14][15] a je slabší než permutační skupina problém izomorfismu a problém průniku permutační skupiny. U posledních dvou problémů Babai, Kantor & Luks (1983) získané hranice složitosti podobné jako u izomorfismu grafů.

Vyřešené speciální případy

Řada důležitých zvláštních případů problému izomorfismu grafů má efektivní řešení v polynomiálním čase:

• Stromy^[16][17]
• Rovinné grafy^[18] (Ve skutečnosti je izomorfismus rovinného grafu v prostor protokolu,^[19] třída obsažená v P )
• Intervalové grafy^[20]
• Permutační grafy^[21]
• Oběžné grafy^[22]
• Grafy ohraničených parametrů
  • Grafy ohraničené šířka stromu^[23]
  • Grafy ohraničené rod^[24] (Rovinné grafy jsou grafy rodu 0.)
  • Grafy ohraničené stupeň^[25]
  • Grafy s ohraničením vlastní číslo multiplicita^[26]
  • k- Smluvní grafy (zobecnění omezeného stupně a omezeného rodu)^[27]
  • Izomorfismus zachovávající barvu barevné grafy s omezenou multiplicitou barev (tj. maximálně k vrcholy mají stejnou barvu pro pevné k) je ve třídě NC, což je podtřída P^[28]

Třída složitosti GI

Vzhledem k tomu, že problém isomorfismu grafu není ani známý jako NP-úplný, ani známý jako traktovatelný, vědci se snažili získat vhled do problému definováním nové třídy GI, soubor problémů s a polynomiálně-Turingova redukce k problému izomorfismu grafu.^[29] Pokud je problém izomorfismu grafu řešitelný v polynomiálním čase, GI by se rovnal P. Na druhou stranu, pokud je problém NP-úplný, GI by se rovnal NP a všechny problémy v NP by bylo řešitelné v kvazi-polynomiálním čase.

Jak je běžné pro třídy složitosti v rámci polynomiální časová hierarchie se nazývá problém GI-těžké pokud existuje polynomiálně-Turingova redukce z jakéhokoli problému v GI k tomuto problému, tj. řešení polynomiálního času problému GI-hard, by přineslo řešení polynomiálního času problému izomorfismu grafu (a tak všechny problémy v GI). Problém ${ displaystyle X}$ je nazýván kompletní pro GInebo GI-kompletní, pokud je to GI-tvrdé a polynomiálně-časové řešení problému GI by přineslo polynomiálně-časové řešení pro ${ displaystyle X}$.

Problém izomorfismu grafu je obsažen v obou NP aDOPOLEDNE. GI je obsažen v a nízký pro Parita P, jakož i obsaženy v potenciálně mnohem menší třídě SPP.^[30] To, že leží v paritě P, znamená, že problém isomorfismu grafu není o nic těžší než určit, zda je polynomiální čas nedeterministický Turingův stroj má sudý nebo lichý počet přijímacích cest. GI je také obsažen v a low for ZPP^NP.^[31] To v podstatě znamená, že efektivní Algoritmus Las Vegas s přístupem k NP věštec dokáže vyřešit izomorfismus grafů tak snadno, že nezíská žádnou moc, když mu bude dána schopnost tak činit v konstantním čase.

GI-úplné a GI-tvrdé problémy

Izomorfismus jiných předmětů

Existuje celá řada tříd matematických objektů, pro které je problém izomorfismu problémem s úplným GI. Řada z nich jsou grafy vybavené dalšími vlastnostmi nebo omezeními:^[32]

• digrafy^[32]
• označené grafy s podmínkou, že k uchování štítků není nutný izomorfismus,^[32] ale jen vztah ekvivalence skládající se z dvojic vrcholů se stejným štítkem
• "polarizované grafy" (vyrobené z a kompletní graf K._m a prázdný graf K._n plus některé hrany spojující dva; jejich izomorfismus musí zachovat oddíl)^[32]
• 2-barevné grafy^[32]
• výslovně dané konečné struktur^[32]
• multigrafy^[32]
• hypergrafy^[32]
• konečné automaty^[32]
• Markovské rozhodovací procesy^[33]
• komutativní třída 3 nilpotentní (tj., xyz = 0 pro každý prvek X, y, z) poloskupiny^[32]
• konečná hodnost asociativní algebry přes pevné algebraicky uzavřené pole s nulovým čtvercovým radikálem a komutativním faktorem nad radikálem.^[32][34]
• bezkontextové gramatiky^[32]
• vyvážené neúplné návrhy bloků^[32]
• Uznávám kombinatorický izomorfismus z konvexní polytopes reprezentované výskytem vrcholů-fazet.^[35]

GI-kompletní třídy grafů

Třída grafů se nazývá GI-Complete, pokud je rozpoznání izomorfismu pro grafy z této podtřídy problémem GI-Complete. Následující třídy jsou kompletní GI:^[32]

• spojené grafy^[32]
• grafy průměr 2 a poloměr 1^[32]
• směrované acyklické grafy^[32]
• pravidelné grafy^[32]
• bipartitní grafy bez netriviální silně pravidelné podgrafy^[32]
• bipartitní Euleriánské grafy^[32]
• bipartitní pravidelné grafy^[32]
• spojnicové grafy^[32]
• rozdělené grafy^[36]
• chordální grafy^[32]
• pravidelný samo-doplňkové grafy^[32]
• polytopální grafy obecně, jednoduchý, a zjednodušující konvexní polytopes v libovolných rozměrech.^[37]

Mnoho tříd digrafů je také úplných GI.

Další GI-úplné problémy

Kromě problémů s izomorfismem existují další netriviální problémy s GI.

• Uznání autokomplementarity grafu nebo digrafu.^[38]
• A klika problém pro třídu tzv M-grafy. Je prokázáno, že nalezení izomorfismu pro n-vertexové grafy jsou ekvivalentní hledání n-klika v M- graf velikosti n². Tato skutečnost je zajímavá, protože problém nalezení (n − ε) -klika v a M- graf velikosti n² je NP-úplný pro libovolně malé kladné ε.^[39]
• Problém homeomorfismu 2-komplexů.^[40]

GI-těžké problémy

• Problém spočítání počtu izomorfismů mezi dvěma grafy je v polynomiálním čase ekvivalentní problému zjištění, zda vůbec existuje.^[41]
• Problém rozhodování, zda dva konvexní polytopes dané buď V-popis nebo H-popis jsou projektivně nebo afinně izomorfní. Ten druhý znamená existenci projektivní nebo afinní mapy mezi prostory, které obsahují dva polytopy (ne nutně stejné dimenze), což vyvolává bijekci mezi polytopy.^[37]

Kontrola programu

Manuel Blum a Sampath Kannan (1995 ) ukázaly pravděpodobnostní kontrolu programů pro izomorfismus grafů. Předpokládat P je deklarovaná procedura polynomiálního času, která kontroluje, zda jsou dva grafy izomorfní, ale není důvěryhodná. Chcete-li zkontrolovat, zda G a H jsou izomorfní:

• Zeptat se P zda G a H jsou izomorfní.
  • Pokud je odpověď „ano“:
    • Pokus o konstrukci izomorfismu pomocí P jako podprogram. Označte vrchol u v G a proti v Ha upravte grafy tak, aby byly charakteristické (s malou místní změnou). Zeptat se P pokud jsou upravené grafy izomorfní. Pokud ne, změňte se proti na jiný vrchol. Pokračujte v hledání.
    • Buď bude nalezen izomorfismus (a může být ověřen), nebo P bude si odporovat.
  • Pokud je odpověď „ne“:
    • Proveďte následující stokrát. Vyberte si náhodně G nebo Ha náhodně permutovat jeho vrcholy. Zeptat se P pokud je graf izomorfní s G a H. (Jako v DOPOLEDNE protokol pro neizomorfismus grafů).
    • Pokud některý z testů selže, posuďte P jako neplatný program. Jinak odpovězte „ne“.

Tento postup je polynomiální a dává správnou odpověď, pokud P je správný program pro izomorfismus grafů. Li P není správný program, ale odpovídá správně na G a H, Kontrola buď dá správnou odpověď, nebo zjistí neplatné chování P.Li P není správný program a odpovídá nesprávně G a H, Kontrola detekuje neplatné chování P s vysokou pravděpodobností nebo odpovězte špatně s pravděpodobností 2⁻¹⁰⁰.

Zejména, P se používá pouze jako blackbox.

Aplikace

Grafy se běžně používají ke kódování strukturálních informací v mnoha oblastech, včetně počítačové vidění a rozpoznávání vzorů, a shoda grafu, tj. identifikace podobností mezi grafy, je důležitým nástrojem v těchto oblastech. V těchto oblastech je problém isomorfismu grafů známý jako přesná shoda grafu.^[42]

v cheminformatika a v matematická chemie, testování izomorfismu grafu se používá k identifikaci a chemická sloučenina v rámci chemická databáze.^[43] Také v organické matematické chemii je testování izomorfismu užitečné pro generování molekulární grafy a pro počítačová syntéza.

Chemické vyhledávání v databázi je příkladem grafického dolování dat, Kde kanonizace grafů přístup se často používá.^[44] Zejména řada identifikátory pro chemické substance, jako ÚSMĚVY a InChI, které jsou navrženy tak, aby poskytovaly standardní a člověkem čitelný způsob kódování molekulárních informací a usnadňovaly vyhledávání těchto informací v databázích a na webu, při jejich výpočtu používejte krok kanonizace, což je v podstatě kanonizace grafu, který představuje molekulu.

v elektronická automatizace designu izomorfismus grafu je základem Layout Versus Schematic (LVS) krok návrhu obvodu, což je ověření, zda elektrické obvody zastoupená a obvodové schéma a uspořádání integrovaných obvodů jsou stejní.^[45]

Viz také

• Problém automorfismu grafů
• Kanonizace grafů

Poznámky

Reference