Bidimensionalitet

Bidimensionalitetsteori kännetecknar ett brett spektrum av grafproblem ( bidimensionella ) som tillåter effektiva approximativa, fasta parametrar eller kärnlösningar i ett brett spektrum av grafer. Dessa grafklasser inkluderar plana grafer , kartgrafer, grafer med avgränsat släkte och grafer exklusive fasta mindre. I synnerhet bygger bidimensionalitetsteorin på Robertsons och Seymours mindre grafiska teori genom att utöka de matematiska resultaten och bygga nya algoritmiska verktyg. Teorin introducerades i arbeten av Demaine , Fomin , Hajiaghayi och Thilikos, för vilka författarna fick Nerode-priset 2015.

Definition

Ett parametriserat problem $\Pi$ är en delmängd av $\Gamma ^{*}\times \mathbb {N}$ för något ändligt alfabet $\Gamma$ . En instans av ett parameteriserat problem består av (x,k) , där k kallas parametern.

Ett parameteriserat problem $\Pi$ är mindre tvådimensionellt if

1. För alla grafpar $H,G$ , så att $H$ är en moll av $G$ och heltal $k$ , $(G,k)\in \Pi$ ger att $(H,k)\in \Pi$ . Med andra ord, sammandragning eller radering av en kant i en graf $G$ kan inte öka parametern; och
2. det finns $\delta >0$ så att för varje $(r\times r)$ -rutnät $R$ , $(R,k)\inte \in \Pi$ för varje $k\leq \delta r^{2}$ . Med andra ord bör värdet på lösningen på $R$ vara minst $\delta r^{2}$ .

Exempel på mindre tvådimensionella problem är de parametriserade versionerna av vertex cover , feedback vertex set , minimum maximal matching och längsta väg .

Graf $\Gamma _{6}$

Låt $\Gamma _{r}$ vara grafen som erhålls från $(r\times r)$ -rutnätet genom att triangulera inre ytor så att alla inre hörn blir av grad 6, och sedan ett hörn av grad två förenat med kanter med alla hörn på den yttre sidan. Ett parameteriserat problem $\Pi$ är kontraktions-bidimensionellt if

1. För vilket par av grafer som helst ${\displaystyle H,G} ,$ så att $H$ är en sammandragning av $G$ och heltal $k$ , $(G,k)\in \Pi$ ger att $(H,k)\in \Pi$ . Med andra ord, sammandragning av en kant i en graf $G$ kan inte öka parametern; och
2. det finns $\delta >0$ så att $(\Gamma _{r},k)\inte \in \Pi$ för varje ${ \displaystyle k\leq \delta r^{2}}$ .

Exempel på kontraktions-bidimensionella problem är dominerande uppsättning , ansluten dominerande uppsättning , max-bladspännande träd och kantdominerande uppsättning .

Exkluderade rutnätssatser

Alla algoritmiska tillämpningar av bidimensionalitet är baserade på följande kombinatoriska egenskap: antingen är trädbredden på en graf liten eller så innehåller grafen ett stort rutnät som en mindre eller sammandragning. Mer exakt,

1. Det finns en funktion f så att varje graf G exklusive en fast h -vertex-graf som en moll och med trädbredd minst f(h)r innehåller (rxr) -rutnät som en moll.
2. Det finns en funktion g så att varje graf G exklusive en fast h -vertex apex-graf som en moll och med trädbredd minst g(h) r kan kantkontrakteras till $\Gamma _{r}$ .

Halins rutnätssats är en analog utesluten rutnätsats för oändliga grafer.

Subexponentiella parametriserade algoritmer

Låt $\Pi$ vara ett mindre tvådimensionellt problem så att för vilken graf G som helst , exklusive någon fast graf som en moll och med trädbredd som mest t , avgör om $(G,k) )\in \Pi$ kan göras i tiden $2^{O(t)}\cdot |G|^{O(1)}$ . Sedan för varje graf G exklusive någon fast graf som moll, bestämmer du om $(G,k)\in \Pi$ kan göras i tiden $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ . På liknande sätt, för tvådimensionella kontraktionsproblem, för graf G exklusive någon fast apexgraf som en mindre, kan inkludering $(G,k)\in \Pi$ bestämmas i tiden $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ .

Således är många tvådimensionella problem som Vertex Cover, Dominating Set, k-Path lösbara i tiden $2^{O({\sqrt {k}})}\cdot |G|^{O(1)}$ på grafer exklusive någon fast graf som moll.

Polynomtidsapproximationsscheman

Bidimensionalitetsteori har använts för att erhålla polynom-tidsapproximationsscheman för många tvådimensionella problem. Om ett mindre (sammandragning) tvådimensionellt problem har flera ytterligare egenskaper, utgör problemet effektiva polynom-tidsapproximationsscheman på (apex) molfria grafer.

I synnerhet genom att använda tvådimensionalitet visade det sig att återkopplingspunktuppsättning , vertextäcke , ansluten vertexkåpa, cykelpackning, diamantslagningssats, maximal inducerad skog, maximal inducerad tvådelad subgraf och maximal inducerad plan subgraf medger en EPTAS på H- mindre fria grafer. Kantdominerande uppsättning, dominerande uppsättning , r-dominerande uppsättning, ansluten dominerande uppsättning, r-spridd uppsättning, minsta maximal matchning, oberoende uppsättning , maximal fullgradig spannträd, maximal inducerad högst d-graders subgraf, maximal intern spännträd, inducerad matchning , triangelpackning, partiell r-dominerande uppsättning och partiell vertextäckning tillåter en EPTAS på apex-minor-fria grafer.

Kernelisering

Huvudartikel: Kernelisering

Ett parametriserat problem med en parameter k sägs tillåta en linjär vertexkärna om det finns en polynom tidsreduktion, kallad en kerneliseringsalgoritm , som mappar ingångsinstansen till en likvärdig instans med som mest O(k) hörn.

Varje mindre tvådimensionellt problem $\Pi$ med ytterligare egenskaper, nämligen med separationsegenskapen och med ändligt heltalsindex, har en linjär vertexkärna på grafer som exkluderar någon fast graf som en moll. På liknande sätt har varje kontraktions-bidimensionellt problem $\Pi$ med separationsegenskapen och med ändligt heltalsindex en linjär vertexkärna på grafer som exkluderar någon fast apexgraf som moll.

Anteckningar

•   Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H -moll-free graphs", J. ACM , 52 (6): 866–893, arXiv : 1104.2230 , doi : 5/31101 ,812101 ,812101 S2CID 6238832 .
•   Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2004), "Bidimensional parameters and local treewidth", SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX 10.1.1.81.9021 , doi : 10.1137/S010344.301054 .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) , s. 590–601 .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008a), "Linearity of grid minors in treewidth with applications through bidimensionality", Combinatorica , 28 ( 1): 19–36, doi : 10.1007/s00493-008-2140-4 1 62C01ID   .
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008b), "The bidimensionality theory and its algorithmic applications", The Computer Journal , 51 (3): 292–302, doi : 10.1093/comjnl/bxm033 , hdl : 17209.01/33 .
•   , "A short proof of Halins grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi : 10.1007/BF02941538 , MR 2112834 312 S2834 912 S612834   .
• Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M. (2009), "Contraction Bidimensionality: The Accurate Picture", 17th Annual European Symposium on Algorithms (ESA 2009) , Lecture Notes in Computer Science, vol. 5757, s. 706–717, doi : 10.1007/978-3-642-04128-0_63 .
• Fomin, Fedor V.; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (2011), "Bidimensionality and EPTAS", Proc. 22:a ACM/SIAM-symposiet om diskreta algoritmer (SODA 2011) , s. 748–759, arXiv : 1005.5449 , Bibcode : 2010arXiv1005.5449F .
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M. (2010), "Bidimensionality and Kernels", 21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) , s. 503–510 .

Vidare läsning

•   Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), "Kapitel 7", Parameterized Algorithms , Springer, sid. 612, ISBN 978-3-319-21274-6
•   Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019), "Kapitel 15", Kernelization: Theory of Parameterized Preprocessing , Cambridge University Press, sid. 528, doi : 10.1017/9781107415157 , ISBN 978-1107057760