Generoidun osagraafin isomorfismin ongelma

Generoitu osagraafin isomorfismiongelma on NP-täydellinen ratkaistavuusongelma kompleksisuusteoriassa ja graafiteoriassa . Ongelmana on löytää tietty graafi toisen, suuremman graafin generoituna aligraafina .

Ongelman selvitys

Muodollisesti tehtävän syötteenä on kaksi kuvaajaa ja , jossa pisteiden määrä on pienempi tai yhtä suuri kuin pisteiden määrä . on isomorfinen graafin generoidulle osagraafille, jos on injektio f , joka kuvaa graafin kärjet graafin kärkeen siten, että kaikille V 1 :n pistepareille x , y , reuna ( x , y ) on läsnä E1 : ssä , jos ja vain jos reuna on E2 : ssa . Vastaus päätösongelmaan on kyllä, jos tämä funktio f on olemassa, ja ei muuten. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $V_{1}$ $V_{2}$ $G_{1}$ $G_{2}$ $G_{1}$ $G_{2}$ ${\näyttötyyli (f(x),f(y))}$

Ongelma eroaa osagraafin isomorfismin ongelmasta siinä, että G 1 :n reunan puuttuminen tarkoittaa, että vastaavan reunan G 2 :ssa täytyy myös olla poissa. Aligraafin isomorfismin alla nämä "ylimääräiset" reunat G2 : ssa voivat olla läsnä.

Laskennallinen monimutkaisuus

Generoidun aligraafin isomorfismiongelman monimutkaisuus erottaa ulkotason graafit niiden yleistyksestä, rinnakkaissarjakuvaajista - se voidaan ratkaista polynomiajassa 2-liitetyille ulompitasoisille graafeille, mutta on NP-täydellinen 2-liitetyille rinnakkaissarjakaavioille [1] [2] .

Erikoistilaisuudet

Erikoistapaus pitkän polun löytämisestä hyperkuution generoituna aligraafina on hyvin tutkittu ja sitä kutsutaan käärme laatikossa -tehtäväksi [3] . Suurin riippumaton joukko -ongelma on myös generoitu osagraafin isomorfismitehtävä, jossa suurta riippumatonta joukkoa etsitään suuremman graafin generoituna osagraafina ja suurin klikkiongelma on generoitu aligraafin isomorfismiongelma, jossa graafin suuri klikki etsitään suuremman graafin generoituna aligraafina.

Ero aligraafin isomorfismiongelmasta

Vaikka generoidun aligraafin isomorfismin ongelma näyttää olevan vain hieman erilainen kuin aligraafin isomorfismin ongelma, rajoitus sanaan "syntynyt" aiheuttaa riittävän suuria muutoksia laskennallisen monimutkaisuuden kannalta havaittavissa.

Esimerkiksi aligraafin isomorfismin ongelma on NP-täydellinen yhdistetyissä oikeissa intervallikaavioissa ja yhdistetyissä kaksiosaisissa permutaatiokaavioissa [4] , mutta generoitu osagraafin isomorfismiongelma voidaan ratkaista polynomiajassa näissä kahdessa luokassa [5] .

Lisäksi indusoitu alipuun isomorfismiongelma (eli indusoitu osagraafin isomorfismiongelma, jossa graafityyppiä G 2 rajoittaa puu) voidaan ratkaista polynomiajassa intervalligraafilla, kun taas alipuun isomorfismiongelma on NP-täydellinen ominaisarvoilla. intervallikaaviot [6] .

Muistiinpanot

↑ Sysło, 1982 , s. 91–97.
↑ Johnson, 1985 , s. 434–451.
↑ Ramanujacharyulu, Menon, 1964 , s. 131-135.
↑ Kijima, Otachi, Saitoh, Uno, 2012 , s. 3164–3173.
↑ Heggernes, van't Hof, Meister, Villanger, 2015 .
↑ Heggernes, van't Hof, Milanič, 2013 .

Kirjallisuus

Maciej M. Syslo. Alagraafin isomorfismin ongelma ulompitasoisille graafille // Teoreettinen tietojenkäsittelytiede. - 1982. - T. 17 , no. 1 . - S. 91-97 . - doi : 10.1016/0304-3975(82)90133-5 .
David S Johnson NP-täydellisyyssarake: jatkuva opas // Journal of Algorithms. - 1985. - T. 6 , no. 3 . — S. 434–451 . - doi : 10.1016/0196-6774(85)90012-4 .
Ramanujacharyulu C., Menon VV Huomautus käärme-in-the-box -ongelmasta // Publ. Inst. tilasto. Univ. Pariisi. - 1964. - T. 13 . — S. 131–135 .
Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno. Aligraafin isomorfismi graafiluokissa // Diskreetti matematiikka. - 2012. - marraskuu ( nide 312 , numero 21 ). - doi : 10.1016/j.disc.2012.07.010 .
Pinar Heggernes, Pim van't Hof, Daniel Meister, Yngve Villanger. Indusoitu aligraafin isomorfismi oikeilla intervalli- ja bipartite-permutaatiokaavioilla // Teoreettinen tietojenkäsittelytiede. – 2015.
Pinar Heggernes, Pim van't Hof, Martin Milanic. Indusoidut alipuut intervallikaavioissa // Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA) . – 2013.