Problém hledání izomorfního podgrafu

Problém hledání izomorfního podgrafu je výpočetní problém, ve kterém jsou vstupem dva grafy G a H a je nutné určit, zda G obsahuje podgraf izomorfní ke grafu H . Problém nalezení izomorfního podgrafu je zobecněním jak problému maximální kliky , tak problému kontroly, zda graf obsahuje Hamiltonův cyklus a je tedy NP-úplný [1] . Problémy s nalezením izomorfního podgrafu s některými druhy podgrafů však lze vyřešit v polynomiálním čase [2] [3] .

Někdy se také používá název mapování podgrafů pro stejný problém. Tento název zdůrazňuje nalezení takových podgrafů, nejen rozlišitelnost.

Problém řešitelnosti a výpočetní složitosti

Abychom dokázali, že problém nalezení izomorfního podgrafu je NP-úplný, musí být formulován jako problém řešitelnosti . Vstupem úlohy řešitelnosti je odstavec G a H . Odpověď na problém je kladná, pokud je H izomorfní k nějakému podgrafu G , a jinak záporná.

Formální úkol:

Nechť jsou dva grafy. Existuje takový podgraf ? Tito. existuje takové mapování ?

Důkaz NP-úplnosti problému nalezení izomorfního podgrafu je jednoduchý a spoléhá na redukci na tento problém klikového problému , NP-úplné řešitelnosti, ve které je vstupem jediný graf G a číslo k , a otázkou je, zda graf G obsahuje úplný podgraf s k vrcholy. Abychom tento problém zredukovali na problém nalezení izomorfního podgrafu, jednoduše vezmeme úplný graf K k jako graf H. Pak se odpověď na problém hledání izomorfního podgrafu se vstupními grafy G a H rovná odpovědi na úlohu kliky pro graf G a číslo k . Protože problém kliky je NP-úplný, taková polynomiální redukovatelnost ukazuje, že problém nalezení izomorfního podgrafu je také NP-úplný [4] .

Alternativní redukce z problému hamiltonovského cyklu mapuje graf G , který je testován na hamiltonianitu, na dvojici grafů G a H , kde H je cyklus, který má stejný počet vrcholů jako G . Protože problém Hamiltonova cyklu je NP-úplný i pro rovinné grafy , ukazuje to, že problém nalezení izomorfního podgrafu zůstává NP-úplný i pro rovinný případ [5] .

Problém podgrafu izomorfismu je zobecněním problému izomorfismu grafu , který se ptá, zda je graf G izomorfní s grafem H - odpověď na problém izomorfismu grafu je "ano" tehdy a jen tehdy, když grafy G a H mají stejné počet vrcholů a hran a problém najít izomorfní podgraf pro grafy G a H dává „ano“. Stav problému izomorfismu grafu z hlediska teorie složitosti však zůstává otevřený.

Gröger [6] ukázal, že pokud platí Aandera–Karp–Rosenbergova domněnka o složitosti dotazování monotónních vlastností grafu, pak jakýkoli problém s nalezením izomorfního podgrafu má složitost dotazu Ω( n 3/2 ). To znamená, že řešení problému hledání izomorfního podgrafu vyžaduje kontrolu existence nebo nepřítomnosti na vstupu Ω( n 3/2 ) různých hran grafu [7] .

Algoritmy

Ullman [8] popsal rekurzivní postup zpětného sledování pro řešení problému nalezení izomorfního podgrafu. Ačkoli doba běhu tohoto algoritmu je obecně exponenciální, běží v polynomiálním čase pro jakékoli pevné H (to znamená, že doba běhu je omezena polynomem v závislosti na volbě H ). Je-li G rovinný graf (nebo obecněji graf s omezeným rozšířením ) a H je neměnné, lze dobu řešení úlohy izomorfního podgrafu redukovat na lineární čas [2] [3] .

Ullman [9] významně aktualizoval algoritmus z článku z roku 1976.

Aplikace

Problém hledání izomorfního podgrafu byl aplikován v oblasti chemoinformatiky k hledání podobnosti chemických sloučenin podle jejich strukturních vzorců. V této oblasti se často používá termín vyhledávání podstruktur [8] . Struktura dotazu je často definována graficky pomocí editoru struktury . Databáze založené na SMILES obvykle definují dotazy pomocí SMARTS , rozšíření SMILES .

Úzce související problémy počítání počtu izomorfních kopií grafu H ve větším grafu G se používají pro detekci vzorů v databázích [10] , v bioinformatice protein-protein interakce [11] a v metodách exponenciálních náhodných grafů pro matematické modelování. sociálních sítí [ 12] .

Olrich, Ebeling, Gieting a Sater [13] popsali aplikaci problému hledání izomorfních podgrafů v počítačově podporovaném návrhu elektronických obvodů . Úloha porovnávání podgrafů je také dílčím krokem transformace grafu (vyžaduje nejdelší dobu provádění), a proto je zajišťována pracovním stolem transformace grafů.

Úloha je zajímavá i v oblasti umělé inteligence , kde je považována za součást skupiny úloh přiřazování grafových vzorů . V této oblasti je také zvažováno rozšíření problému hledání izomorfního grafu, známé jako grafová analýza [14] .

Poznámky

  1. ↑ V Cookově původním článku ( Cook 1971 ), obsahujícím důkaz Cook-Levinovy ​​věty , již bylo ukázáno, že problém nalezení izomorfního podgrafu je NP-úplný redukcí z problému 3-SAT pomocí klik .
  2. ↑ 1 2 Eppstein, 1999 , s. 1–27.
  3. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , str. 400–401.
  4. ↑ Wegener, 2005 , str. 81.
  5. ↑ de la Higuera, Janodet, Samuel, Damiand, Solnon, 2013 , str. 76–99.
  6. ↑ Gröger, 1992 , s. 119–127.
  7. ↑ Zde je Ω velká Omega .
  8. ↑ 1 2 Ullmann, 1976 , str. 31–42.
  9. ↑ Ullmann, 2010 .
  10. ↑ Kuramochi, Karypis, 2001 , str. 313.
  11. ↑ Pržulj, Corneil, Jurisica, 2006 , str. 974–980.
  12. ↑ Snijders, Pattison, Robins, Handcock, 2006 , str. 99–153.
  13. ↑ Ohlrich, Ebeling, Ginting, Sather, 1993 , str. 31–37.
  14. ↑ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf Archivováno 29. srpna 2017 na Wayback Machine ; rozšířená verze na https://e-reports-ext.llnl.gov/pdf/332302.pdf Archivováno 31. ledna 2017 na Wayback Machine

Literatura