Problemet med isomorfism till en genererad subgraf

Det genererade subgrafisomorfismproblemet är ett NP-komplett lösbarhetsproblem inom komplexitetsteori och grafteori . Problemet är att hitta en given graf som en genererad subgraf till en annan, större graf.

Förklaring av problemet

Formellt tar problemet som input två grafer och , där antalet hörn i är mindre än eller lika med antalet hörn i . är isomorf till en genererad subgraf i en graf om det finns en injektion f som mappar grafens hörn till grafens vertex så att för alla par av hörn x , y i V 1 , en kant ( x , y ) är förekommer i E 1 om och endast om en kant finns i E2 . Svaret på beslutsproblemet är ja om denna funktion f finns, och nej annars. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $V_{1}$ $V_{2}$ $G_{1}$ $G_{2}$ $G_{1}$ $G_{2}$ $(f(x),f(y))$

Problemet skiljer sig från subgrafisomorfismproblemet genom att frånvaron av en kant i G 1 innebär att motsvarande kant i G 2 också måste vara frånvarande. Under en subgrafisomorfism kan dessa "extra" kanter i G 2 vara närvarande.

Beräkningskomplexitet

Komplexiteten i det genererade subgrafisomorfismproblemet skiljer ytterplanära grafer från deras generalisering, parallell-seriegrafer - det kan lösas i polynomtid för 2-kopplade ytterplanära grafer, men är NP-komplett för 2-kopplade parallell-seriella grafer [1] [2] .

Särskilda tillfällen

Det speciella fallet att hitta en lång väg som en genererad subgraf av en hyperkub är väl studerat och kallas ormen i en låda- problem [3] . Det största problemet med oberoende uppsättningar är också ett genererat subgrafisomorfismproblem, där en stor oberoende uppsättning söks som en genererad subgraf av en större graf, och det största klickproblemet är ett genererat subgrafisomorfismproblem, där en stor klick av en graf söks som en genererad subgraf till en större graf.

Skillnad från subgraph isomorphism problem

Även om problemet med isomorfism till en genererad subgraf bara tycks skilja sig något från problemet med isomorfism till en subgraf, orsakar begränsningen av ordet "född" förändringar som är tillräckligt stora för att märkas ur beräkningskomplexitetssynpunkt.

Till exempel är subgrafisomorfismproblemet NP-komplett på anslutna korrekta intervallgrafer och på anslutna tvådelade permutationsgrafer [4] , men det genererade subgrafisomorfismproblemet kan lösas i polynomtid på dessa två klasser [5] .

Dessutom kan problemet med inducerad subträdisomorfism (d.v.s. problemet med inducerad subgrafisomorfism, där graftypen G 2 avgränsas av ett träd) lösas i polynomtid på intervallgrafer, medan subträdets isomorfismproblem är NP-komplett på egenvärden. intervallgrafer [6] .

Anteckningar

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

Litteratur

Maciej M. Syslo. Subgrafens isomorfismproblem för ytterplanära grafer // Teoretisk datavetenskap. - 1982. - T. 17 , nr. 1 . — S. 91–97 . - doi : 10.1016/0304-3975(82)90133-5 .
David S Johnson Kolumnen NP-fullständighet: en pågående guide // Journal of Algorithms. - 1985. - T. 6 , nr. 3 . — S. 434–451 . - doi : 10.1016/0196-6774(85)90012-4 .
Ramanujacharyulu C., Menon VV En anteckning om problemet med orm-i-lådan // Publ. Inst. statistik. Univ. Paris. - 1964. - T. 13 . — S. 131–135 .
Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno. Subgrafisomorfism i grafklasser // Diskret matematik. - 2012. - November ( vol. 312 , nummer 21 ). - doi : 10.1016/j.disc.2012.07.010 .
Pinar Heggernes, Pim van't Hof, Daniel Meister, Yngve Villanger. Inducerad subgrafisomorfism på korrekta intervall- och tvådelade permutationsgrafer // Teoretisk datavetenskap. — 2015.
Pinar Heggernes, Pim van't Hof, Martin Milanic. Inducerade underträd i intervallgrafer // Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA) . — 2013.