Problém izomorfismu podgrafu - Subgraph isomorphism problem - Wikipedia

v teoretická informatika, podgraf izomorfismus problém je výpočetní úkol, ve kterém dva grafy G a H jsou uvedeny jako vstup a je třeba určit, zda G obsahuje a podgraf to je izomorfní na H.Izografický izomorfismus je zobecněním obou maximální problém s klikou a problém testování, zda graf obsahuje a Hamiltonovský cyklus, a proto je NP-kompletní.^[1] Některé další případy izomorfismu podgrafu však lze vyřešit v polynomiálním čase.^[2]

Někdy jméno shoda podgrafu se také používá pro stejný problém. Toto jméno klade důraz na nalezení takového podgrafu na rozdíl od problému holého rozhodnutí.

Rozhodovací problém a výpočetní složitost

Aby se prokázalo, že izomorfismus podgrafu je NP-úplný, musí být formulován jako a rozhodovací problém. Vstupem do rozhodovacího problému je dvojice grafů G a H. Odpověď na problém je kladná, pokud H je izomorfní s podgrafem Ga jinak negativní.

Formální otázka:

Nechat ${ displaystyle G = (V, E)}$ , ${ displaystyle H = (V ^ { prime}, E ^ { prime})}$ být grafy. Existuje podgraf ${ displaystyle G_ {0} = (V_ {0}, E_ {0}) mid V_ {0} subseteq V, E_ {0} subseteq E cap (V_ {0} krát V_ {0}) }$ takhle ${ displaystyle G_ {0} cong H}$ ? I. e., Existuje a bijekce ${ displaystyle f colon V_ {0} rightarrow V ^ { prime}}$ takhle ${ displaystyle {, v_ {1}, v_ {2} , } v E_ {0} iff {, f (v_ {1}), f (v_ {2}) , } v E ^ { prime}}$ ?

Důkaz, že izomorfismus podgrafu je NP-úplný, je jednoduchý a je založen na redukci klika problém, NP-úplný rozhodovací problém, ve kterém je vstupem jediný graf G a číslo k, a otázkou je, zda G obsahuje a kompletní podgraf s k vrcholy. Chcete-li to přeložit na problém izomorfismu podgrafu, jednoduše to nechte H být úplným grafem K._k; pak odpověď na problém izomorfismu podgrafu pro G a H se rovná odpovědi na problém s klikou pro G a k. Jelikož problém s klikami je NP-úplný, toto polynomial-time many-one reduction ukazuje, že izomorfismus podgrafu je také NP-úplný.^[3]

Alternativní snížení z Hamiltonovský cyklus problém překládá graf G který má být testován na Hamiltonicity do dvojice grafů G a H, kde H je cyklus se stejným počtem vrcholů jako G. Protože problém Hamiltonovského cyklu je NP-úplný i pro rovinné grafy, to ukazuje, že izomorfismus podgrafu zůstává NP-úplný i v rovinném případě.^[4]

Podgraf izomorfismus je zobecněním problém grafového izomorfismu, který se ptá, zda G je izomorfní s H: odpověď na problém isomorfismu grafu je pravdivá, právě když G a H oba mají stejný počet vrcholů a hran a problém izomorfismu podgrafu pro G a H je pravda. Teoretický stav složitosti izomorfismu grafů však zůstává otevřenou otázkou.

V kontextu Aanderaa – Karp – Rosenbergova domněnka na složitost dotazu vlastností monotónního grafu, Gröger (1992) ukázalo, že jakýkoli problém izomorfismu podgrafu má složitost dotazu Ω (n^3/2); tj. řešení izomorfismu podgrafu vyžaduje algoritmus ke kontrole přítomnosti nebo nepřítomnosti na vstupu Ω (n^3/2) různé hrany v grafu.^[5]

Algoritmy

Ullmann (1976) popisuje postup rekurzivního zpětného sledování pro řešení problému izomorfismu podgrafu. I když jeho doba běhu je obecně exponenciální, trvá polynomiální čas pro jakoukoli pevnou volbu H (s polynomem, který závisí na výběru H). Když G je rovinný graf (nebo obecněji graf ohraničená expanze ) a H je pevná, lze dobu běhu izomorfismu podgrafu zkrátit na lineární čas.^[2]

Ullmann (2010) je podstatnou aktualizací článku o izomorfismu podgrafu z roku 1976.

Cordella (2004) v roce 2004 navrhl další algoritmus založený na Ullmannově, VF2, který vylepšuje proces upřesňování pomocí různých heuristik a využívá podstatně méně paměti.

Bonnici (2013) navrhl lepší algoritmus, který pomocí počáteční heuristiky vylepšuje počáteční pořadí vrcholů.

U velkých grafů zahrnují nejmodernější algoritmy CFL-Match a Turboiso a jejich rozšíření, například DAF od Han (2019).

Aplikace

Jako podgraf izomorfismus byl použit v oblasti cheminformatika najít podobnosti mezi chemickými sloučeninami z jejich strukturního vzorce; často v této oblasti termín vyhledávání spodní stavby se používá.^[6] Struktura dotazu je často definována graficky pomocí a editor struktury program; ÚSMĚVY založené databázové systémy obvykle definují dotazy pomocí SMARTS, a ÚSMĚVY rozšíření.

Úzce související problém počítání počtu izomorfních kopií grafu H ve větším grafu G byl použit k zjišťování vzorů v databázích,^[7] the bioinformatika interakčních sítí protein-protein,^[8] a v exponenciální náhodný graf metody matematického modelování sociální sítě.^[9]

Ohlrich a kol. (1993) popsat aplikaci izomorfismu podgrafu v počítačem podporovaný design z elektronické obvody. Subpart shoda je také dílčím krokem přepis grafu (nejnáročnější na běh), a proto je nabízí nástroje pro přepis grafů.

Problém je také zajímavý umělá inteligence, kde je považován za součást řady porovnávání vzorů v grafech problémy; rozšíření izomorfismu podgrafu známé jako těžba grafů je také zajímavý v této oblasti.^[10]

Viz také

Poznámky

^ Originál Cook (1971) papír, který dokazuje Cook – Levinova věta již ukázal izomorfismus podgrafu jako NP-úplný, s použitím redukce z 3-SAT zahrnující kliky.
^ ^A ^b Eppstein (1999); Nešetřil & Ossona de Mendez (2012)
^ Wegener, Ingo (2005), Teorie složitosti: Zkoumání mezí efektivních algoritmů, Springer, str. 81, ISBN 9783540210450.
^ de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013), "Polynomiální algoritmy pro otevřené izomorfismy grafů a podgrafů" (PDF), Teoretická informatika, 498: 76–99, doi:10.1016 / j.tcs.2013.05.026, PAN 3083515, Od poloviny 70. let je známo, že problém izomorfismu je pro rovinné grafy řešitelný v polynomiálním čase. Bylo však také poznamenáno, že problém subisomorfismu je stále NP úplný, zejména proto, že problém Hamiltonovského cyklu je NP-úplný pro rovinné grafy.
^ Zde Ω vyvolá Velká nota Omega.
^ Ullmann (1976)
^ Kuramochi & Karypis (2001).
^ Pržulj, Corneil a Jurisica (2006).
^ Snijders a kol. (2006).
^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; rozšířená verze na https://e-reports-ext.llnl.gov/pdf/332302.pdf

Reference

Cook, S.A. (1971), „Složitost postupů dokazujících věty“, Proc. 3. ACM symposium o teorii práce na počítači, str. 151–158, doi:10.1145/800157.805047.
Eppstein, David (1999), "Podgraf izomorfismus v rovinných grafech a související problémy" (PDF), Journal of Graph Algorithms and Applications, 3 (3): 1–27, arXiv:cs.DS / 9911003, doi:10,7155 / jgaa 00014.
Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN 978-0-7167-1045-5. A1.4: GT48, s. 202.
Gröger, Hans Dietmar (1992), „O randomizované složitosti vlastností monotónního grafu“ (PDF), Acta Cybernetica, 10 (3): 119–127.
Han, Myoungji; Kim, Hyunjoon; Gu, Geonmo; Park, Kunsoo; Han, Wookshin (2019), „Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set together“, SIGMOD, doi:10.1145/3299869.3319880
Kuramochi, Michihiro; Karypis, George (2001), „Časté objevování podgrafů“, 1. mezinárodní konference IEEE o dolování dat, str. 313, CiteSeerX 10.1.1.22.4992, doi:10.1109 / ICDM.2001.989534, ISBN 978-0-7695-1119-1.
Ohlrich, Miles; Ebeling, Carl; Ginting, Eka; Sather, Lisa (1993), „SubGemini: identifikace subcircuits pomocí algoritmu izomorfismu rychlého podgrafu“, Sborník z 30. mezinárodní konference Automation Design, str. 31–37, doi:10.1145/157485.164556, ISBN 978-0-89791-577-9.
Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „18.3 Problém izomorfismu podgrafu a booleovské dotazy“, Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Springer, str. 400–401, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, PAN 2920058.
Pržulj, N .; Corneil, D. G.; Jurisica, I. (2006), „Efektivní odhad frekvenčních distribucí grafů v interakčních sítích protein-protein“, Bioinformatika, 22 (8): 974–980, doi:10.1093 / bioinformatika / btl030, PMID 16452112.
Snijders, T. A. B .; Pattison, P.E .; Robins, G .; Handcock, M. S. (2006), „Nové specifikace pro exponenciální modely náhodných grafů“, Sociologická metodologie, 36 (1): 99–153, CiteSeerX 10.1.1.62.7975, doi:10.1111 / j.1467-9531.2006.00176.x.
Ullmann, Julian R. (1976), „Algoritmus pro izomorfismus podgrafu“, Deník ACM, 23 (1): 31–42, doi:10.1145/321921.321925.
Jamil, Hasan (2011), „Computing Subgraph Isomorphic Queries using Structural Unification and Minimum Graph Structures“, 26. ACM Symposium on Applied Computing, str. 1058–1063.
Ullmann, Julian R. (2010), „Algoritmy bitových vektorů pro uspokojení binárních omezení a izomorfismus podgrafu“, Journal of Experimental Algorithmics, 15: 1.1, CiteSeerX 10.1.1.681.8766, doi:10.1145/1671970.1921702.
Cordella, Luigi P. (2004), „Algoritmus (sub) grafového izomorfismu pro porovnávání velkých grafů“, Transakce IEEE na analýze vzorů a strojové inteligenci, 26 (10): 1367–1372, CiteSeerX 10.1.1.101.5342, doi:10.1109 / tpami.2004.75, PMID 15641723
Bonnici, V .; Giugno, R. (2013), „Algoritmus izomorfismu podgrafu a jeho aplikace na biochemická data“, BMC bioinformatika, 14 (Suppl7) (13): S13, doi:10.1186 / 1471-2105-14-s7-s13, PMC 3633016, PMID 23815292
Carletti, V .; Foggia, P .; Saggese, A .; Vento, M. (2018), „Výzva k časové složitosti izomorfismu přesného podgrafu pro obrovské a husté grafy s VF3“, Transakce IEEE na analýze vzorů a strojové inteligenci, 40 (4): 804–818, doi:10.1109 / TPAMI.2017.2696940

[1] Originál Cook (1971) papír, který dokazuje Cook – Levinova věta již ukázal izomorfismus podgrafu jako NP-úplný, s použitím redukce z 3-SAT zahrnující kliky.

[e99-2] A ^b Eppstein (1999); Nešetřil & Ossona de Mendez (2012)

[3] Wegener, Ingo (2005), Teorie složitosti: Zkoumání mezí efektivních algoritmů, Springer, str. 81, ISBN 9783540210450.

[4] Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon, Christine (2013), "Polynomiální algoritmy pro otevřené izomorfismy grafů a podgrafů" (PDF), Teoretická informatika, 498: 76–99, doi:10.1016 / j.tcs.2013.05.026, PAN 3083515, Od poloviny 70. let je známo, že problém izomorfismu je pro rovinné grafy řešitelný v polynomiálním čase. Bylo však také poznamenáno, že problém subisomorfismu je stále NP úplný, zejména proto, že problém Hamiltonovského cyklu je NP-úplný pro rovinné grafy.

[5] Zde Ω vyvolá Velká nota Omega.

[6] Ullmann (1976)

[7] Kuramochi & Karypis (2001).

[8] Pržulj, Corneil a Jurisica (2006).

[9] Snijders a kol. (2006).

[10] ttp://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; rozšířená verze na https://e-reports-ext.llnl.gov/pdf/332302.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]