Planar partitionssats

Planar partitionssatsen  är en form av den isoperimetriska olikheten för plana grafer , som säger att vilken plan graf som helst kan delas upp i mindre bitar genom att ta bort ett litet antal hörn. I synnerhet, genom att ta bort O(√ n ) hörn från en graf med n hörn (här står O för "stor O" ), kan man dela upp grafen i frånkopplade subgrafer , som var och en har högst 2 n /3 hörn.

En svagare planar partitionssats med O(√ n  log  n ) hörn i separatorn istället för O(√ n ) bevisades av Ungar ( Ungar 1951 ), och en teorem med en starkare asymptotisk bunden på separatorns storlek bevisades först av Lipton och Tarjan ( Lipton och Tarjan 1979). ). Sedan deras artiklar har planar partitionssatsen bevisats på nytt på flera olika sätt, och O(√ n ) konstanten i satssatsen har förbättrats. Teoremet har också utvidgats till vissa klasser av icke-planära grafer.

Om du återapplicerar partitioneringssatsen får du en separatorhierarki, som kan ha formen av antingen en trädupplösning eller en grengrafupplösning . Separatorhierarkin kan användas för att utveckla effektiva " Dela och erövra " algoritmer för plana grafer, och dynamisk programmering på dessa hierarkier kan användas för att utveckla exponentiell tid och lösbara med fasta parametrar för att lösa NP-hårda optimeringsproblem på dessa grafer. Separatorhierarkin kan också användas i kapslad dissektion , en effektiv variant av Gauss eliminering för att lösa glesa system av linjära algebraiska ekvationer som uppstår i finita elementmetoden .

Teorin om tvådimensionalitet Eric Demain , Fedor Fomin, Mohammed Hadjigaya och Dimitros Tilikos generaliserar och utökar avsevärt omfattningen av planar uppdelningssatsen till en stor uppsättning problem på plana grafer och mer allmänt på grafer som gör det. inte innehålla en viss minderårig .

Uttalande av satsen

I sin vanliga formulering säger planar partitionssatsen att i varje plan graf G  = ( V , E ) med n hörn finns det en uppdelning av G :s hörn i tre uppsättningar A , S och B så att var och en av mängderna A och B har maximalt 2 n /3 hörn, S har O(√ n ) hörn, och det finns inga kanter som har en ände i A och den andra änden i B . Det krävs inte att A eller B är sammankopplade subgrafer av G . Uppsättningen S kallas en separator för denna partition.

En ekvivalent formulering är att kanterna på vilken plan graf G som helst med n hörn kan delas upp i två subgrafer G 1 och G 2 som inte är förbundna med kanter på ett sådant sätt att båda subgraferna har minst n /3 hörn, medan skärningen av vertexuppsättningar av dessa två subgrafer har O(√ n ) hörn. En sådan split är känd som en split [1] . Om en frånkoppling ges, bildar skärningen av vertexuppsättningar en separator, och hörn som hör till en subgraf men inte till en annan bildar två delmängder med högst 2 n /3 hörn. Omvänt, om en partition i tre uppsättningar A , S och B ges som uppfyller villkoren för planar partitionssatsen, så kan man bilda en frånkoppling där kanterna med ändarna i A tillhör G 1 , kanterna med ändarna i B tillhör G 2 , och de återstående kanterna kanter (med båda ändarna i S ) kan ingå i vilken som helst av uppsättningarna.

Konstanten 2/3 i satssatsen är godtycklig och kan ersättas med vilket annat tal som helst från det öppna intervallet (1/2,1) utan att ändra formen på satsen - en partition i delmängder av mer lika storlek kan vara erhålls från mindre identiska partitioner genom att ompartitionera en större uppsättning i ojämna delar och omarrangemang av de resulterande anslutna komponenterna [2] .

Exempel

Betrakta ett gitter med r rader och c kolumner. Antalet n hörn i detta gitter är lika med rc . Till exempel i figuren är r  = 5, c  = 8 och n  = 40. Om r är udda finns det en enda mittrad, annars finns det två rader lika nära mitten. På samma sätt, om c är udda, finns det en enda mittkolumn, annars finns det två kolumner på samma avstånd från mitten. Genom att välja dessa centrala rader och kolumner som S och ta bort S från grafen delar vi upp grafen i två mindre sammankopplade subgrafer A och B , som var och en har högst n /2 hörn. Om r  ≤  c (som i figuren), kommer valet av mittkolumnen att ge en avgränsare S med r  ≤ √ n hörn, och på liknande sätt, om c  ≤  r , kommer att välja mittraden ge en avgränsare med högst √ n hörn. Varje gittergraf har alltså en separator S med högst √ n hörn, vars borttagande delar upp grafen i två sammankopplade komponenter, vars storlek inte överstiger n /2 [3] .

Planar partitionssatsen säger att en liknande partition kan konstrueras för vilken plan graf som helst. Fallet med en godtycklig plan graf skiljer sig från gittergrafen genom att i det här fallet har separatorn storleken O(√ n ), som kan vara större än talet √ n , och storlekarna på två delmängder A och B (högst vanlig version av satsen) inte överstiga 2 n / 3, inte n / 2, som för gittergrafer. Dessutom bildar delmängder A och B inte nödvändigtvis kopplade subgrafer.

Byggnader

Paket

Lipton och Tarjan [4] förstorar en given plan graf genom att lägga till kanter vid behov, så att den blir en maximal plan graf (varje sida av en plan inbäddning är en triangel). Sedan gör de en breddsökning med början vid en godtycklig vertex v och delar upp hörnen i nivåer enligt deras avstånd från v . Om l 1 är en median (en nivå för vilken antalet hörn över och under den inte överstiger n /2), måste det finnas nivåerna l 0 och l 2 som är O(√ n ) steg över och under l 1 som innehåller O (√ n ) hörn, annars finns det fler än n hörn nära nivån l 1 . De visade att det måste finnas en separator S bildad av föreningen av l 0 och l 2 och ändarna av kanterna på grafen G som ligger mellan dessa två nivåer. Storleken på separatorn S konstruerad på detta sätt överstiger inte √8√n , vilket är ungefär 2,83√n . Hörnen av separatorn och två partitionsuppsättningar kan hittas i linjär tid .

Detta bevis för planar partitioneringssatsen gäller också för viktade plana grafer när varje vertex har en icke-negativ kostnad. Grafen kan delas in i tre uppsättningar A , S och B , så att A och B kostar högst 2/3 av det fulla priset, och S har O(√ n ) hörn utan kanter från A till B [4] . Genom att analysera sådana konstruktioner av separatorer mer noggrant visade Dzhidzhev [2] att storleksgränsen S kan reduceras till √6√ n , vilket är ungefär lika med 2,45√ n .

Holzer, Schultz Wagner, Prasinos och Zaroligis [5] föreslog en förenklad version av tillvägagångssättet - de utökar grafen till en maximal plan graf och utför en sökning på bredden först på samma sätt som beskrivits ovan. Sedan bildar de för varje kant e som inte hör till sökträdet en slinga genom att kombinera e med stigar i trädet som förbinder kantens ändar. Sedan använder de en av dessa slingor som en vertexseparator. Även om detta tillvägagångssätt inte garanterar att hitta en liten separator för plana grafer med stor diameter, visar deras experiment att detta tillvägagångssätt fungerar bättre än Lipton-Tarjan och Didzhev-fibreringsmetoderna på många typer av plana grafer.

Enkla separeringscykler

För en graf som redan är maximal plan kan man visa en rigorös konstruktion av en enkel cykelseparator , en cykel av liten längd vars inre och yttre delar (för en viss plan inbäddning) inte har mer än 2n /3 hörn. Miller [6] bevisade detta (med en separator av storleken √8√ n ) med hjälp av Lipton-Tarjan-tekniken för en modifierad version av bredd-först-sökning där nivåerna bildar enkla cykler.

Alon, Seymour och Thomas [7] bevisade existensen av en enkel cykelavskiljare på ett mer direkt sätt – de ansåg cyklerna C med högst √8√ n hörn som har högst 2 n /3 hörn utanför C och sedan bildades en skiljevägg i så många som möjligt närmare delar innanför och utanför slingan. De visade att under alla dessa förhållanden skulle C behöva vara en separator. Annars måste avstånden inuti C vara lika med avstånden i skivan omsluten av C (den kortaste vägen genom insidan av skivan skulle utgöra en del av den bästa cykelgränsen). Dessutom måste cykeln C ha längden exakt √8√ n , annars kan den förbättras genom att ersätta en av kanterna med de andra två sidorna av triangeln. Om hörn av cykel C är numrerade (medurs) från 1 till √8√ n och vertex i motsvarar vertex √8√ n − i + 1 , då kan dessa par av hörn sammankopplas med icke-korsande banor inuti skivan (enligt en av formerna av Mengers sats för plana grafer). Den totala längden av dessa banor skulle emellertid överstiga n , en motsägelse. Efter några ytterligare beräkningar visade de, med liknande metoder, att det finns en enkel cykelseparator med storleken som mest (3/√2)√ n , vilket är ungefär lika med 2,12√ n .

Jijev och Venkatesan [8] förbättrade senare konstanten i den enkla cykelseparatorsatsen till 1,97√ n . Deras metod gör det också möjligt att söka efter enkla cykelseparatorer för grafer med icke-negativa vertexvikter med en separatorstorlek som inte överstiger 2√n . Metoden låter dig skapa separatorer med en mindre storlek, dock på grund av den större skillnaden i storlekarna på partitionens delar. I en 2-kopplad icke-maximal plan graf finns en enkel separatorcykel med en storlek proportionell mot den euklidiska normen för ansiktslängdsvektorn, som kan hittas i nästan linjär tid [9] .

Cykelavgränsare

Enligt Koebe-Andreev-Thurstons cirkelpackningssats kan vilken plan graf som helst representeras som en packning av cirklar i ett plan med icke-korsande inre områden, så att två hörn av grafen är intill varandra om och endast om motsvarande cirklar rör vid varandra . Som Miller, Teng, Thurston och Wawasis [10] visade , för sådana packningar finns det en cirkel som berörs eller ligger inuti den, inte mer än 3 n /4 skivor, inte mer än 3 n /4 skivor ligger utanför cirkeln, eller rör vid den, och som skär O(√ n ) skivor.

För att bevisa detta använde Miller et al. stereografisk projektion för att kartlägga packningen på ytan av en enda 3D-sfär. Med noggrant val av projektion kan sfärens centrum placeras vid mittpunkten av mitten av ytans skivor, så att varje plan som passerar genom sfärens mitt kommer att dela sfären i två halvklot, vardera av vilka innehåller eller skär högst 3 n /4 skivor. Om planet genom mitten väljs slumpmässigt och enhetligt, kommer skivan att skäras med en sannolikhet som är proportionell mot radien. Således är det förväntade antalet korsade skivor proportionellt mot summan av skivornas radier. Summan av kvadratradier är dock proportionell mot skivornas totala yta, som inte överstiger ytarean av en enhetssfär, en konstant. Argument som använder Jensens olikhet visar att om summan av kvadrater av n icke-negativa tal begränsas av en konstant, överstiger summan av själva talen inte O(√ n ). Således är förväntan på antalet skärningar av skivor med ett slumpmässigt plan O(√ n ) och det finns ett plan som inte skär mer än detta antal skivor. Detta plan skär sfären i en storcirkel , vars projektion tillbaka på planet ger de önskade egenskaperna. O(√ n )-skivorna som skärs av denna cirkel motsvarar hörnen på den plana grafseparatorn, som skiljer de hörn vars skivor ligger innanför cirkeln från de hörn vars skivor ligger utanför cirkeln, och var och en av dessa delmängder har högst 3 n /4 hörn [10] [11] .

Denna metod leder till en probabilistisk algoritm som hittar en separator i linjär tid [10] och en mindre praktisk deterministisk algoritm med samma linjära tidsgräns [12] . Genom att noggrant analysera denna algoritm och använda de kända gränserna för packningstätheten av cirklar , kan det visas att det är möjligt att hitta separatorer som inte överstiger i storlek

[13]

Även om denna förbättrade separatorstorlek resulterar i mer ojämlik uppdelning av grafen, hävdar Shpilman och Teng [14] att metoden ger en förbättrad multiplikator i körtiden för kapslad partitionering jämfört med separatorn Alon, Seymour och Thomas [1] . Storleken på separatorerna kan i praktiken förbättras genom att använda en ojämn fördelning av slumpmässiga skärplan [15] .

Den stereografiska projektionen i argumentet från Miller et al kan undvikas genom att betrakta den minsta cirkeln som innehåller en konstant bråkdel av skivcentra, och sedan expandera med en mängd som väljs enhetligt i intervallet [1,2]. Det är lätt att visa, som i Millers, att skivorna som korsas av en sådan cirkel bildar en regelbunden separator, och då kommer den matematiska förväntningen på antalet skärningar att ge det korrekta resultatet. Det är sant att de resulterande konstanterna blir något sämre [16] .

Spektral partitionering

Spektralklustringsmetoder , där grafens hörn grupperas enligt egenvärdeskoordinaterna för matriser som erhålls från grafen, har länge använts som heuristiska metoder för att lösa grafpartitioneringsproblem för icke-plana grafer [ 17] [18] . Som Shpilman och Teng [19] har visat , kan spektrala klustringar också användas för att alternativt bevisa en försvagad form av planar partitionssatsen tillämpad på plana grafer med avgränsad vertexgrad. I deras metod sorteras hörnen för en given plan graf efter den andra koordinaten för egenvektorerna för Kirchhoff-matrisen i grafen, och denna ordning delas vid en punkt som minimerar förhållandet mellan antalet avlägsnade kanter och antalet kanter. hörn på den mindre delen av partitionen. Som de visade har varje plan graf med en avgränsad grad av hörn en partition där detta förhållande är O(1/√ n ). Även om denna partition kanske inte är balanserad, resulterar upprepning av partitionen av den största av de två delarna och sammanslagning av skärningarna som erhålls vid varje iteration i slutändan i en balanserad partition med O(√ n ) kanter. Ändens toppar av dessa kanter bildar en separator av storlek (√ n ).

Ribbavskiljare

En variant av plan sönderdelningssatsen talar om kantseparatorer , små uppsättningar kanter som bildar ett snitt mellan två delmängder A och B i en grafs hörn. De två uppsättningarna, A och B , måste ha en storlek som högst är en konstant bråkdel av antalet n hörn i grafen (vanligtvis krävs att båda uppsättningarna inte är större än 2 n /3), och varje vertex i grafen tillhör till endast A eller B. Avskiljaren består av kanter som har ena änden i A och den andra änden i B . Kantseparatorns storleksgränser beror både på graden av grafens hörn och på antalet hörn i de grafiska plana graferna, där en vertex har graden n  − 1, där hjul och stjärnor faller , inte har en separator med en sublinjär antal kanter, eftersom varje kantavskiljare bör inkludera alla kanter som förbinder en höggradig vertex med hörn på andra sidan av snittet. Varje plan graf med maximal grad Δ har dock en kantseparator med storleken O(√(Δ n )) [20]

En enkel cykelseparator i den dubbla grafen i en plan graf bildar en kantseparator för den ursprungliga grafen [6] [9] . Att tillämpa den enkla cykelseparatorsatsen för Gacit och Miller [9] på den dubbla grafen för en given plan graf stärker O(√(Δ n ))-uppskattningen för kantseparatorns storlek, eftersom den visar att vilken plan graf som helst har en kantseparator vars storlek är proportionell mot den euklidiska normen för vektorvertexgraderna i grafen.

Papadimitrou och Sideri [21] beskrev en polynom-tidsalgoritm för att hitta en kantseparator som delar en graf G i två subgrafer av samma storlek om G är en genererad subgraf av en gittergraf utan hål eller med ett konstant antal hål. De antog dock att problemet är NP-komplett för fallet med godtyckliga plana grafer, och visade att komplexiteten i problemet för gittergrafer med ett godtyckligt antal hål är densamma som för godtyckliga plana grafer.

Nedre gränser

I gittergrafen √ n  × √ n kan mängden S som innehåller s  < √ n punkter omge en delmängd av högst s ( s  − 1)/2 punkter av gittret, och det maximala uppnås genom att placera S på diagonalen linje närmare hörnet av gallret. För att bilda en separator som separerar minst n /3 punkter från rutnätet måste s alltså ha en storlek på minst √(2 n /3), vilket är ungefär 0,82√ n .

Det finns plana grafer med n hörn (för godtyckligt stora värden på n ) så att för varje separator S som delar upp den återstående grafen i subgrafer med högst 2n /3 hörn, har S minst √(4π√3)√ n hörn, ca 1,56√ n [2] . Konstruktionen använder en approximation av en sfär med en konvex polyeder genom att ersätta varje yta av polyederen med ett triangulärt nät. Den isoperimetriska satsen appliceras sedan på ytan av en sfär.

Separatorhierarkier

Separatorer kan kombineras till en plan grafseparatorhierarki , en rekursiv uppdelning till mindre grafer. Separatorhierarkin kan representeras som ett binärt träd , där roten representerar själva grafen, och de två underordnade noderna till roten är rötterna till de genererade subgraferna av delmängder A och B i den rekursivt konstruerade separatorhierarkin.

Hierarkin av separatorer av denna typ utgör grunden för en trädnedbrytning av en given graf, där uppsättningen av hörn som är associerade med en trädnod är föreningen av separatorer på vägen från denna nod till trädets rot. Eftersom storleken på graferna minskar med en konstant faktor på varje nivå i trädet, minskar även de övre gränserna för storleken på separatorerna med en konstant faktor på varje nivå, så att storlekarna på separatorerna längs dessa banor adderas exponentiellt till O(√ n ). Det vill säga att den sålunda bildade separatorn har bredden O(√ n ) och denna kan användas för att visa att vilken plan graf som helst har trädbredden O(√ n ).

Att bygga en separatorhierarki direkt genom att korsa det binära trädet från topp till botten och använda en linjär tidsalgoritm för att hitta en plan separator till var och en av de genererade subgraferna som är associerade med varje nod i det binära trädet skulle ta total tid O( n  log  n ) . Det är dock möjligt att bygga hela separatorhierarkin i linjär tid om vi använder Lipton-Tarjans breddfibreringsmetod och använder lämpliga datastrukturer för att implementera varje partitioneringssteg i sublinjär tid [22] .

Om vi ​​bildar hierarkier baserade inte på separatorer, utan på frånkopplingar, där två underordnade hörn blir rötter för den rekursiva konstruktionen av separatorhierarkier för två subgrafer G 1 och G 2 av separationen av en given graf, så bildar den fullständiga strukturen en nedbrytning av grafen i grenar , och inte en trädnedbrytning. Bredden av varje uppdelning i denna sönderdelning är återigen begränsad av summan av storleken på separatorerna på vägen från valfri nod till roten av hierarkin, så att varje sönderdelning som erhålls på detta sätt har bredden O(√ n ) och vilken plan graf som helst har grenbredd O(√ n ). Även om många andra relaterade grafpartitioneringsproblem är NP-kompletta även för plana grafer, är det möjligt att hitta en nedbrytning av en plan graf till grenar med minsta bredd i polynomtid [23] .

Genom att tillämpa metoderna från Alon, Seymour och Thomas [7] mer direkt för att konstruera en grafnedbrytning till grenar, visade Fomin och Tilikos [24] att varje plan graf har en förgreningsbredd som inte överstiger 2,12√ n , det vill säga med samma konstant som för uppdelningssatsen av Alon Alon, Seymour och Thomas med enkla cykelseparatorer. Eftersom trädbredden på vilken graf som helst är högst 3/2 av grenbredden, visar detta också att plana grafer har en trädbredd på högst 3,18√ n .

Andra klasser av grafer

Vissa glesa grafer har inte sublinjära storleksseparatorer - i en expander lämnar man bort en konstant bråkdel av hörn en ansluten komponent [4] [25] .

Den kanske tidigaste partitioneringssatsen är Jordans resultat [26] att vilket träd som helst kan delas upp i två underträd med högst n /2 hörn i varje genom att ta bort en enda vertex [10] . I synnerhet har spetsen som minimerar storleken på den maximala komponenten denna egenskap. Genom att tillämpa samma teknik på trädnedbrytningen av en godtycklig graf, kan det visas att varje graf har en separator med en storlek som inte överstiger dess trädbredd .

Om grafen G inte är plan, utan kan vara inbäddad i en yta av släktet g , så har den en separator med O(( gn ) 1/2 ) hörn. Gilbert, Hutchinson och Tarjan [27] bevisade detta genom att använda ett tillvägagångssätt som liknar Lipton och Tarjans [4] . De grupperar grafens hörn efter bredd-första söknivåer och hittar två nivåer vars borttagning lämnar högst en stor komponent bestående av ett litet antal nivåer. Denna återstående komponent kan göras plan genom att ta bort ett antal bredd-första sökvägar proportionellt mot grafens släkte, varefter Lipton-Tarjan-metoden kan tillämpas på den återstående plana grafen. Resultatet erhålls genom att noggrant balansera storleken på de borttagna två nivåerna och antalet nivåer mellan dem. Givet en grafinbäddning kan dess separator hittas i linjär tid . Grafer av släktet g har separatorer med storleken O(( g Δ n ) 1/2 ) [28] .

Grafer av begränsat släkte bildar ett exempel på en familj av grafer som stängs under driften av att ta minderåriga , och partitionssatser gäller för godtyckliga familjer av grafer som stängs för att ta en mindreårig. I synnerhet, om en familj av grafer har en förbjuden moll med h hörn, så har den en separator med O( h √ n ) hörn, och en sådan separator kan hittas i O( n 1 + ε ) tid för alla ε > 0 [29]

Metoden för separatorcykler för Miller, Teng, Thurston och Vavasis [10] är generaliserad för skärningsgraferna för alla system av d -dimensionella kulor, som har egenskapen att vilken punkt på ytan som helst täcks av kulor som mest någon konstant antal k gånger, för grafer k - närmaste grannar i rummet med dimensionen d [10] , och för grafer som uppstår i finita elementraster [30] . Sfäriska separatorer konstruerade på detta sätt delar upp ingångsgrafen i subgrafer med högst n ( d + 1)/( d + 2) hörn. Storleken på separatorer för grafer av k -faldiga överlappande bollar och grafer för k -närmaste grannar är O( k 1/ d n 1 − 1/ d ) [10] .

Applikationer

Dela och erövra algoritmer

Separatorpartitioner kan användas för att bygga effektiva " Dela och erövra "-algoritmer för att lösa problem på plana grafer. Ett exempel på ett problem som kan lösas med detta tillvägagångssätt är att hitta den kortaste cykeln i en vägd planriktad graf. Du kan göra så här:

Tiden för två rekursiva anrop för A och B i denna algoritm domineras av O(√ n ) körtiden för Dijkstras algoritm, så denna algoritm hittar den kortaste cykeln i O( n 3/2  log  n ) tid.

En snabbare algoritm för samma problem att hitta den kortaste cykeln, löpande i tiden O( n  log 3 n ), gavs av Wolf-Nielsen [31] . Hans algoritm använder samma dela-och-härska-struktur baserad på separatorer, men använder enkla cykelseparatorer istället för godtyckliga separatorer, så att hörn av mängden S tillhör samma yta (för den inre grafen och för den yttre grafen med respekt till separatorn). Den ersätter sedan O(√ n ) individuella anrop till Dijkstras algoritm med mer sofistikerade algoritmer för att hitta kortaste vägar från alla hörn på en enda sida av en plan graf och kombinera avstånd från två subgrafer. För vägda men oriktade plana grafer är den kortaste cykeln ekvivalent med det minsta snittet i den dubbla grafen och kan hittas i O( n  log log  n ) tid [32] , och den kortaste cykeln i en vägd cykel oriktad plan graf (dess omkrets ) kan hittas i tiden O( n ) [33] . (Den snabbare algoritmen för oviktade grafer är dock inte baserad på partitionssatsen.)

Frederickson föreslog 1986 en annan snabb algoritm för den kortaste vägen från en enda källa genom att använda partitioneringssatsen för plana grafer [34] . Algoritmen är en förbättring av Dijkstras iterativa sökning på en noggrant utvald delmängd av hörn. Denna version körs i O( n √(log n )) tid på en graf med n hörn. Separatorer används för att hitta uppdelningen av en graf, det vill säga dess uppdelning i två eller flera delmängder, kallade områden. En nod sägs vara innesluten i en region om någon kant av regionen faller in mot noden. En nod som finns i mer än ett område kallas gränsnoden för de områden som innehåller den. Metoden använder begreppet en r -division av en graf med n noder, vilket motsvarar att dela upp grafen i O( n / r )-regioner, som var och en innehåller O( r )-noder, inklusive O(√ r ) gränsnoder . Frederickson visade att r -divisionen kan hittas i O( n log n ) tid genom att rekursivt tillämpa partitionssatsen.

Översikt över algoritmen för att lösa problemet.

1. Preliminär förberedelse . Vi delar upp grafen i noggrant utvalda delmängder av hörn och hittar de kortaste vägarna mellan alla par av hörn i dessa delmängder, där vägens mellanliggande hörn inte tillhör delmängden. I denna fas är det nödvändigt att omvandla den plana grafen G 0   till G , som inte har några hörn med grad större än 3. Från Euler- formeln kommer antalet hörn i den resulterande grafen att vara n ≤ 6 n 0  −12, där n 0   är antalet hörn i grafen G 0  . Denna fas ger också följande egenskaper hos lämpliga r- delningar. En lämplig r -division av en plan graf är en r -division sådan att

2. Sök

Henzinger et al utökade Fredericksons r -divisionsteknik för algoritmen för att hitta den kortaste vägen från en enda källa i plana grafer med icke-negativa kantlängder och föreslog en linjär tidsalgoritm [35] . Deras metod generaliserar uppfattningen om en Fredrekson-partition för en graf, så att nu en ( r , s )-partition av en graf med n noder blir en partition i O( n / r )-regioner, som var och en innehåller r {O(1) }   noder och högst s gränsnoder. Om ( r , s )-partitionen upprepas sekventiellt för att dela upp i mindre områden, kallas detta en rekursiv partition. Algoritmen använder ungefär log* n divisionsnivåer. Rekursiv division representeras av ett rotat träd vars löv är märkta med olika kanter på grafen G. Trädets rot representerar regionen som består av hela grafen G , rotens barn representerar de underregioner som regionen är indelad i. Varje blad representerar exakt en kant.

Kapslad dissektion  är en separatorbaserad variant av dela-och-härska-metoden till den Gaussiska elimineringsmetoden för att lösa glesa symmetriska system av linjära algebraiska ekvationer med en plan grafstruktur, såsom uppstår i den finita elementmetoden . Metoden använder sökningen efter en separator för ekvationsbeskrivningsgrafen, exkluderar rekursivt variabler i två deluppgifter separerade från varandra av en separator, och exkluderar sedan variablerna i separatorn [36] . Beläggningen av denna metod (antalet koefficienter som inte är noll för den resulterande Cholesky-expansionen för en matris) är O( n  log  n ) [37] [38] , vilket gör att denna metod kan konkurrera med iterativa metoder för samma problem [ 36] .

Klein, Moses och Weimann [39] föreslog en O( n log 2  n ) linjär minnesalgoritm för att hitta de kortaste avstånden från s för alla noder i en riktad plan graf med positiva och negativa båglängder som inte innehåller negativa cykler. Deras algoritm använder plana grafseparatorer för att hitta en Jordan-kurva C som går genom O(√ n )-noder (men inte genom bågar) så att mellan n /3 och 2 n /3-noder är inuti (området som begränsas av den stängda) kurvan C . Noderna genom vilka kurvan C passerar är gränsnoder . Den ursprungliga grafen G är uppdelad i två subgrafer Go och   G1 , som skär av den plana inbäddningen längs kurvan C och duplicerar gränsnoderna . För i =0 och 1, i Gi ligger gränsnoderna i   en sida av Fi  .

En översikt över detta tillvägagångssätt ges nedan.

En viktig del av denna algoritm är användningen av funktionerna Pris och Reduced Length. För en riktad graf G med båglängder ι(•) är kostnadsfunktionen funktionen φ från noderna i grafen G till de reella talen . För en båge uv är den reducerade längden med avseende på φ ιφ( uv )=ι( uv ) + φ( u ) − φ( v ). En tillåten kostnadsfunktion är en funktion som ger icke-negativa reducerade längder på alla bågar av G . Det är användbart att konvertera ett problem med kortaste vägen som har både positiva och negativa båglängder till ett problem med icke-negativa längder, vilket gör att Dijkstras algoritm kan användas.

Det separatorbaserade dela-och-härska-paradigmet används också för att utveckla datastrukturer för dynamiska grafalgoritmer [40] [41] och punktlokalisering [42] , polygontrianguleringsalgoritmer [ 22] , kortaste vägar [ 43] [44] , för att konstruera närmaste granngrafer [45] och approximationsalgoritmer för att hitta den maximala oberoende uppsättningen på plana grafer [42] .

Exakt lösning av NP-hårda optimeringsproblem

När man använder dynamisk programmering på träddekomposition eller grennedbrytning för en plan graf kan många klasser av NP-hårda optimeringsproblem lösas exponentiellt i tid beroende på √ n eller √ n  log  n . Till exempel är gränser av detta slag kända för att söka efter maximala oberoende uppsättningar , Steinerträd , Hamiltonska cykler och för att lösa problemet med resande försäljare på plana grafer [46] . Liknande metoder som använder partitioneringssatser för geometriska grafer kan användas för att lösa det euklidiska resandeförsäljarproblemet och bygga ett Steinerträd inom samma tidsgränser [47] .

För parameteriserade -problem som tillåter parametrisk reduktion som bevarar planaritet och reducerar indatafilen till en kärna med en storlek som beror linjärt på parametern, kan detta tillvägagångssätt användas för att konstruera fast-parametriskt lösbara -algoritmer vars exekveringstid beror på polynomiskt på storleken på ingångsgrafen och exponentiellt i √ k , där k  är en parameter för algoritmen. Till exempel är körtidsgränser av detta slag kända för att hitta vertextäcken och dominerande uppsättningar av storlek k [48] [49] .

Approximationsalgoritmer

Lipton och Tarjan [42] observerade att partitionssatsen kan användas för att härleda polynom-tidsapproximationsscheman för NP-hårda optimeringsproblem på plana grafer, såsom att hitta den maximala oberoende uppsättningen . I synnerhet, genom att trunkera separatorhierarkin på en lämplig plats, kan man hitta en separator med storleken O( n /√log  n ), vars borttagning delar upp grafen i subgrafer med storleken c  log  n för vilken konstant c som helst . Genom fyrafärgssatsen finns det en oberoende uppsättning av storleken minst n /4, så de borttagna noderna bildar en liten del av den maximala oberoende uppsättningen, och de maximala oberoende uppsättningarna i de återstående subgraferna kan hittas oberoende i exponentiellt tidsberoende på deras storlek. Genom att kombinera detta tillvägagångssätt med linjärtidsmetoderna för att konstruera en separatorhierarki [22] med en tabelluppslagning för att minska tiden för sökning efter oberoende mängder i isomorfa subgrafer, kan man konstruera oberoende mängder som avviker från optimala med en faktor 1 − O(1/√log  n ) i linjär tid. Men för garanterad effektivitet ännu närmare 1 än denna faktor ger Bakers ( Baker 1994 ) senare tillvägagångssätt (baserat på trädnedbrytning snarare än plana separatorer) en bättre kompromiss mellan tid och approximationskvalitet.

Liknande approximationsscheman baserade på konstruktionen av separatorer används för att approximera andra svåra problem, såsom vertextäckningsproblemet [50] [51] . Arora, Grigni, Karger, Klein och Voloshin [52] använde separatorer på ett annat sätt för att approximera problemet med resande säljare för den kortaste vägen på vägda plana grafer. Deras algoritm använder dynamisk programmering för att hitta den kortaste vägen som, på varje nivå i separatorhierarkin, korsar separatorn ett begränsat antal gånger. De visade att när gränsen för antalet korsningar ökar, har de på detta sätt konstruerade sträckorna en längd som är ungefär den optimala sträckan.

Grafkomprimering

Separatorer används som en del av datakomprimeringsalgoritmer för att representera plana grafer och andra separerbara grafer med ett litet antal bitar. Huvudprincipen för dessa algoritmer är att välja ett nummer k och dela upp den givna plana grafen med hjälp av separatorer i O( n / k ) subgrafer av högst k , med O( n /√k ) hörn i separatorerna. Med ett lämpligt val av k (maximalt proportionellt mot logaritmen av n ), är antalet icke-isomorfa plana subgrafer med k hörn väsentligt mindre än antalet subgrafer i sönderdelningen, så graferna kan komprimeras genom att konstruera en tabell över alla möjliga icke-isomorfa subgrafer och representerar varje subgraf i nedbrytningen med ett index i tabellen. Resten av grafen som bildas av avskiljarens hörn kan representeras explicit eller med en rekursiv version av samma datastruktur. Med denna metod kan plana grafer och mer begränsade familjer av plana grafer kodas med det optimala antalet bitar (i termer av informationsteori ) - om det finns grafer P n med n hörn i en graffamilj, då en enskild graf från familj kan representeras med bara (1 + o( n ))log 2 P n bitar [53] . Man kan också bygga vyer av denna typ, där man kan kontrollera närliggande hörn, bestämma graden av en vertex och lista vertexgrannar i konstant tid (per fråga), genom att utöka subgraftabellen med ytterligare information med data motsvarande frågor [54] [55] .

Universella grafer

En universell graf för en graffamilj F  är en graf som innehåller vilket element som helst av familjen F som en subgraf. Separatorer kan användas för att visa att n-vertex plana grafer har en universell graf med n hörn och O( n 3/2 ) kanter [56] .

Konstruktionen använder en starkare form av partitionssatsen, där storleken på de tre delmängderna av hörn i partitionen inte beror på grafens struktur - det finns ett tal c , vars värde är en konstant faktor större än √ n , så att hörnen för varje plan graf med n hörn kan delas in i delmängder A , S och B utan kanter från A till B och med dimensioner | S | =  c , | A | = | b | = ( n  -  c )/2. Detta kan visas genom att applicera den vanliga formen av partitioneringssatsen upprepade gånger på de resulterande partitionerna i grafen tills alla komponenter i partitionen är samlade i två delmängder, som var och en är mindre än n /2 hörn i storlek, och sedan överföra hörn från dessa delmängder till separatorn tills den inte kommer att ha den givna storleken.

Nu kan denna sats användas för att erhålla en separatorhierarki för en plan graf med n hörn, som återigen är oberoende av grafens struktur - trädsönderdelningen som erhålls från denna hierarki är O(√ n ) bred och kan användas för alla plan graf. Uppsättningen av alla par av hörn i denna trädnedbrytning, där var och en av de två hörnen tillhör en gemensam nod av trädnedbrytningen, bildar en trivialt perfekt graf med O( n 3/2 ) hörn, som innehåller vilken plan graf som helst med n hörn som en subgraf. En liknande konstruktion visar att plana grafer av begränsad grad har universella grafer med O( n  log  n ) kanter, där konstanten som döljs i O -notationen beror på grafens grad. Alla universella grafer för plana grafer (eller till och med för träd med obegränsad grad) måste ha Ω( n  log  n ) kanter, men det är fortfarande okänt om denna nedre gräns eller O( n 3/2 ) övre gräns är skarp för universella grafer för godtyckliga plana grafer [56] .

Se även

Anteckningar

  1. ↑ 1 2 Alon, Seymour, Thomas, 1990 .
  2. ↑ 1 2 3 Djidjev, 1982 .
  3. ↑ George, 1973 . Istället för att använda rader och kolumner som en separator för att dela grafen, använder George deras förening och delar upp grafen i fyra delar.
  4. ↑ 1 2 3 4 Lipton, Tarjan, 1979 .
  5. ↑ Holzer, Schulz, Wagner, Prasinos, Zaroliagis, 2009 .
  6. ↑ 12 Miller , 1986 .
  7. ↑ 1 2 Alon, Seymour, Thomas, 1994 .
  8. ↑ Djidjev, Venkatesan, 1997 .
  9. ↑ 1 2 3 Gazit, Miller, 1990 .
  10. ↑ 1 2 3 4 5 6 7 Miller, Teng, Thurston, Vavasis, 1997 .
  11. ↑ Pach, Agarwal, 1995 .
  12. ↑ Eppstein, Miller, Teng, 1995 .
  13. ↑ Spielman, Teng (1996 ).
  14. ↑ Spielman, Teng, 1996 .
  15. ↑ Gremban, Miller, Teng, 1997 .
  16. ↑ Har-Peled, 2011 .
  17. ↑ Donath, Hoffman, 1972 .
  18. ↑ Fiedler, 1973 .
  19. ↑ Spielman, Teng, 2007 .
  20. ↑ Miller ( Miller 1986 ) bevisade detta resultat för 2-kopplade plana grafer, medan Diks, Djidjev, Sýkora, Vrt'o (1993 ) utökade resultatet till alla plana grafer.
  21. ↑ Papadimitriou, Sideri, 1996 .
  22. ↑ 1 2 3 Goodrich, 1995 .
  23. ↑ Seymour, Thomas, 1994 .
  24. ↑ Fomin, Thilikos, 2006a .
  25. ↑ Erdős, Graham, Szemerédi, 1976 .
  26. ↑ Jordanien, 1869 .
  27. ↑ Gilbert, Hutchinson, Tarjan, 1984 .
  28. ↑ Sykora, Vrt'o, 1993 .
  29. ↑ Kawarabayashi, Reed, 2010 . Tidigare arbete på separatorer av mindre slutna familjer - Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, Wood, 2009 .
  30. ↑ Miller, Teng, Thurston, Vavasis, 1998 .
  31. ↑ Wulff-Nilsen, 2009 .
  32. ↑ Łącki, Sankowski, 2011 .
  33. ↑ Chang, Lu, 2011 .
  34. ↑ Frederickson, 1987 , sid. 1004-1022.
  35. ↑ Henzinger, Klein, Rao, Subramanian, 1997 .
  36. ↑ 12 George, 1973 .
  37. ↑ Lipton, Rose, Tarjan, 1979 .
  38. ↑ Gilbert, Tarjan, 1986 .
  39. ↑ Klein, Mozes, Weimann, 2009 .
  40. ↑ Eppstein, Galil, Italiano, Spencer, 1996 .
  41. ↑ Eppstein, Galil, Italiano, Spencer, 1998 .
  42. ↑ 1 2 3 Lipton, Tarjan, 1980 .
  43. ↑ Klein, Rao, Rauch, Subramanian, 1994 .
  44. ↑ Tazari, Müller-Hannemann, 2009 .
  45. ↑ Frieze, Miller, Teng, 1992 .
  46. ↑ Bern, 1990 ; Deĭneko, Klinz, Woeginger, 2006 ; Dorn, Penninkx, Bodlaender, Fomin, 2005 ; Lipton, Tarjan, 1980 .
  47. ↑ Smith, Wormald, 1998 .
  48. ↑ Alber, Fernau, Niedermeier, 2003 .
  49. ↑ Fomin, Thilikos, 2006b .
  50. ↑ Bar-Yehuda, Even, 1982 .
  51. ↑ Chiba, Nishizeki, Saito, 1981 .
  52. ↑ Arora, Grigni, Karger, Klein, Woloszyn, 1998 .
  53. ↑ He, Kao, Lu, 2000 .
  54. ↑ Blandford, Blelloch, Kash, 2003 .
  55. ↑ Blelloch, Farzan, 2010 .
  56. ↑ 1 2 Babai, Chung, Erdős, Graham, Spencer, 1982 ; Bhatt, Chung, Leighton, Rosenberg, 1989 ; Chung, 1990 .

Litteratur