Planar partitionssætning

Planar partitionssætningen  er en form for den isoperimetriske ulighed for plane grafer , som siger, at enhver plan graf kan brydes op i mindre stykker ved at fjerne et lille antal hjørner. Især ved at fjerne O(√ n ) toppunkter fra en graf med n toppunkter (her står O for "large O" ), kan man opdele grafen i afbrudte subgrafer , som hver især har højst 2 n /3 toppunkter.

En svagere planar partitionssætning med O(√ n  log  n ) toppunkter i separatoren i stedet for O(√ n ) blev bevist af Ungar ( Ungar 1951 ), og en sætning med en stærkere asymptotisk bundet til størrelsen af ​​separatoren blev først bevist af Lipton og Tarjan ( Lipton og Tarjan 1979). ). Siden deres papirer er planar partitionssætningen blevet genbevist på flere forskellige måder, og O(√ n ) konstanten i sætningssætningen er blevet forbedret. Sætningen er også blevet udvidet til nogle klasser af ikke-planære grafer.

Genanvendelse af partitioneringssætningen giver et separatorhierarki, som kan tage form af enten en trænedbrydning eller grengrafnedbrydning . Separatorhierarkiet kan bruges til at udvikle effektive " Del og hersk " algoritmer til plane grafer, og dynamisk programmering på disse hierarkier kan bruges til at udvikle eksponentiel tid og løselige med faste parametre til at løse NP-hårde optimeringsproblemer på disse grafer. Separatorhierarkiet kan også bruges i indlejret dissektion , en effektiv variant af Gauss-eliminering til at løse sparsomme systemer af lineære algebraiske ligninger , der opstår i den endelige elementmetode .

Teorien om to-dimensionalitet Eric Demain , Fedor Fomin, Mohammed Hadjigaya og Dimitros Tilikos generaliserer og udvider betydeligt omfanget af planopdelingssætningen til et stort sæt problemer på plane grafer og mere generelt på grafer, der gør det. ikke indeholde en vis mindreårig .

Udtalelse af sætningen

I sin sædvanlige formulering siger planar partitionssætningen, at i enhver plan graf G  = ( V , E ) med n toppunkter eksisterer der en opdeling af toppunkterne af G i tre sæt A , S og B således at hver af mængderne A og B har maksimalt 2 n /3 hjørner, S har O(√ n ) hjørner, og der er ingen kanter, der har den ene ende i A og den anden ende i B. Det er ikke påkrævet, at A eller B er forbundne undergrafer af G. Sættet S kaldes en separator for denne partition.

En ækvivalent formulering er, at kanterne af enhver plan graf G med n toppunkter kan opdeles i to undergrafer G 1 og G 2 , der ikke er forbundet med kanter på en sådan måde, at begge undergrafer har mindst n /3 hjørner, mens skæringspunktet mellem toppunkter i disse to undergrafer har O(√ n ) toppunkter. En sådan opdeling er kendt som en split [1] . Hvis der gives en afbrydelse, danner skæringspunktet mellem toppunkter en separator, og toppunkter, der hører til en undergraf, men ikke til en anden, danner to undergrupper med ikke mere end 2 n /3 hjørner. Omvendt, hvis der gives en partition i tre sæt A , S og B , der opfylder betingelserne for planar partitionssætningen, så kan man danne en afbrydelse, hvor kanterne med enderne i A hører til G 1 , kanterne med enderne i B hører til G 2 , og de resterende kanter kanter (med begge ender i S ) kan indgå i et hvilket som helst af sættene.

Konstanten 2/3 i sætningen af ​​sætningen er vilkårlig og kan erstattes af et hvilket som helst andet tal fra det åbne interval (1/2,1) uden at ændre sætningens form - en opdeling i delmængder af mere ens størrelse kan være opnået fra mindre identiske partitioner ved at ompartitionere et større sæt i ulige dele og omarrangering af de resulterende forbundne komponenter [2] .

Eksempel

Overvej et gitter med r rækker og c kolonner. Antallet n af hjørner af dette gitter er lig med rc . For eksempel på figuren er r  = 5, c  = 8 og n  = 40. Hvis r er ulige, er der en enkelt midterrække, ellers er der to rækker lige tæt på midten. På samme måde, hvis c er ulige, er der en enkelt midtersøjle, ellers er der to kolonner lige langt fra midten. Ved at vælge disse centrale rækker og kolonner som S og fjerne S fra grafen opdeler vi grafen i to mindre forbundne undergrafer A og B , som hver især har højst n /2 hjørner. Hvis r  ≤  c (som på figuren), vil valg af midtersøjlen give en separator S med r  ≤ √ n hjørner, og på samme måde, hvis c  ≤  r , vil valg af midterrækken give en separator med højst √ n hjørner. Enhver gittergraf har således en separator S med højst √ n hjørner, hvis fjernelse deler grafen i to forbundne komponenter, hvis størrelse ikke overstiger n /2 [3] .

Planar partitionssætningen siger, at en lignende partition kan konstrueres for enhver plan graf. Tilfældet med en vilkårlig plan graf adskiller sig fra gittergrafen ved, at separatoren i dette tilfælde har størrelsen O(√ n ), som kan være større end tallet √ n , og størrelsen af ​​to delmængder A og B (i det meste almindelig version af sætningen) ikke overstiger 2 n / 3, ikke n / 2, som for gittergrafer. Delmængderne A og B danner heller ikke nødvendigvis forbundne undergrafer.

Bygninger

Bundle

Lipton og Tarjan [4] forstørrer en given plan graf ved at tilføje kanter, hvis det er nødvendigt, så det bliver en maksimal plan graf (hver side af en plan indlejring er en trekant). Så laver de en søgning i bredden , der starter ved en vilkårlig toppunkt v og opdeler hjørnerne i niveauer i henhold til deres afstand fra v . Hvis l 1 er en median (et niveau, hvor antallet af hjørner over og under det ikke overstiger n /2), så skal der være niveauer l 0 og l 2 , der er O(√ n ) trin over og under l 1 indeholdende O (√ n ) toppunkter, ellers er der mere end n toppunkter nær niveau l 1 . De viste, at der må være en separator S dannet af foreningen af ​​l 0 og l 2 og enderne af kanterne på grafen G , der ligger mellem disse to niveauer. Størrelsen af ​​separatoren S konstrueret på denne måde overstiger ikke √8√ n , hvilket er cirka 2,83√ n . Hjørnerne på separatoren og to partitionssæt kan findes i lineær tid .

Dette bevis for planopdelingssætningen gælder også for vægtede plane grafer, når hvert toppunkt har en ikke-negativ pris. Grafen kan opdeles i tre sæt A , S og B , sådan at A og B højst koster 2/3 af den fulde pris, og S har O(√ n ) hjørner uden kanter fra A til B [4] . Ved at analysere sådanne konstruktioner af separatorer mere omhyggeligt viste Dzhidzhev [2] , at størrelsesgrænsen S kan reduceres til √6√ n , hvilket er omtrent lig med 2,45√ n .

Holzer, Schultz Wagner, Prasinos og Zaroligis [5] foreslog en forenklet version af tilgangen - de udvider grafen til en maksimal plan graf og udfører en bredde-først søgning på samme måde som beskrevet ovenfor. Derefter danner de for hver kant e , der ikke hører til søgetræet, en løkke ved at kombinere e med stier i træet, der forbinder kantens ender. Så bruger de en af ​​disse løkker som topadskiller. Selvom denne tilgang ikke garanterer at finde en lille separator til plane grafer med stor diameter, viser deres eksperimenter, at denne tilgang fungerer bedre end Lipton-Tarjan og Didzhev-fibreringsmetoderne på mange typer plane grafer.

Simple adskillelsescyklusser

For en graf, der allerede er maksimal plan, kan man vise en streng konstruktion af en simpel cyklus-separator , en cyklus af lille længde, hvis indre og ydre dele (for en bestemt plan indlejring) ikke har mere end 2n /3 hjørner. Miller [6] beviste dette (med en separator på størrelse √8√ n ) ved hjælp af Lipton-Tarjan teknikken til en modificeret version af bredde-først søgning, hvor niveauerne danner simple cyklusser.

Alon, Seymour og Thomas [7] beviste eksistensen af ​​en simpel cyklus-separator på en mere direkte måde - de betragtede cyklusser C med højst √8√ n toppunkter, der højst har 2 n /3 toppunkter uden for C , og derefter dannet en skillevæg i så mange som muligt tættere dele inden for og uden for løkken. De viste, at C under alle disse forhold skulle være en separator. Ellers skal afstandene inde i C være lig med afstandene i skiven omsluttet af C (den korteste vej gennem indersiden af ​​skiven ville udgøre en del af den bedste cyklusgrænse). Desuden skal cyklussen C have længden nøjagtigt √8√ n , ellers kan den forbedres ved at erstatte en af ​​kanterne med trekantens to andre sider. Hvis toppunkterne i cyklus C er nummereret (med uret) fra 1 til √8√ n og toppunktet i svarer til toppunktet √8√ n − i + 1 , så kan disse par af toppunkter forbindes af ikke-skærende stier indeni skiven (ifølge en af ​​formerne af Mengers sætning for plane grafer). Imidlertid ville den samlede længde af disse stier overstige n , en modsigelse. Efter nogle yderligere beregninger viste de, ved brug af lignende metoder, at der eksisterer en simpel cyklusseparator af størrelsen på højst (3/√2)√ n , som er omtrent lig med 2,12√ n .

Jijev og Venkatesan [8] forbedrede senere konstanten i den simple cyklusseparatorsætning til 1,97√ n . Deres metode gør det også muligt at søge efter simple cyklusseparatorer for grafer med ikke-negative toppunktsvægte med en separatorstørrelse på ikke over 2√n . Metoden giver dig mulighed for at oprette separatorer med en mindre størrelse, dog på grund af den større forskel i størrelserne på partitionens dele. I en 2-forbundet ikke-maksimal plan graf er der en simpel separator-cyklus med en størrelse proportional med den euklidiske norm for fladelængdevektoren, som kan findes i næsten lineær tid [9] .

Cyklusseparatorer

Ifølge Koebe-Andreev-Thurstons cirkelpakningssætning kan enhver plan graf repræsenteres som en pakning af cirkler i et plan med ikke-skærende indre områder, således at to hjørner af grafen støder op til hinanden, hvis og kun hvis de tilsvarende cirkler berører hinanden. . Som Miller, Teng, Thurston og Wawasis [10] viste , for sådanne pakninger er der en cirkel, der berøres eller ligger inde i den, højst 3 n /4 skiver, ikke mere end 3 n /4 skiver ligger uden for cirklen, eller røre ved den, og som skærer O(√ n ) diske.

For at bevise dette brugte Miller et al. stereografisk projektion til at kortlægge pakningen på overfladen af ​​en enkelt 3D-kugle. Med omhyggeligt valg af projektion kan kuglens centrum placeres i midtpunktet af midten af ​​overfladens skiver, således at ethvert plan, der passerer gennem kuglens centrum vil dele kuglen i to halvkugler, hver hvoraf ikke indeholder eller skærer mere end 3 n /4 diske. Hvis planet gennem midten vælges tilfældigt og ensartet, vil skiven blive skåret med en sandsynlighed proportional med radius. Det forventede antal af krydsede skiver er således proportionalt med summen af ​​skivernes radier. Summen af ​​kvadratiske radier er dog proportional med det samlede areal af skiverne, som ikke overstiger overfladearealet af en enhedskugle, en konstant. Argumenter, der anvender Jensens ulighed , viser, at hvis summen af ​​kvadrater af n ikke-negative tal er afgrænset af en konstant, overstiger summen af ​​selve tallene ikke O(√ n ). Således er forventningen til antallet af skæringer af skiver ved et tilfældigt plan O(√ n ), og der er et plan, der ikke skærer mere end dette antal skiver. Dette plan skærer kuglen i en stor cirkel , hvis projektion tilbage på planet giver de ønskede egenskaber. O(√ n ) skiverne gennemskåret af denne cirkel svarer til hjørnerne af den plane grafseparator, som adskiller de spidser, hvis skiver ligger inde i cirklen, fra de spidser, hvis skiver ligger uden for cirklen, og hver af disse delmængder har højst 3 n /4 hjørner [10] [11] .

Denne metode fører til en probabilistisk algoritme , der finder en separator i lineær tid [10] og en mindre praktisk deterministisk algoritme med den samme lineære tidsgrænse [12] . Ved omhyggeligt at analysere denne algoritme og bruge de kendte grænser for pakningstætheden af ​​cirkler , kan det påvises, at det er muligt at finde separatorer, der ikke overstiger størrelsen

[13]

Selvom denne forbedrede separatorstørrelse resulterer i mere ulige opdeling af grafen, hævder Shpilman og Teng [14] at metoden giver en forbedret multiplikator i køretiden for indlejret partitionering sammenlignet med Alon, Seymour og Thomas separatoren [1] . Størrelsen af ​​separatorerne kan i praksis forbedres ved at anvende en uensartet fordeling af tilfældige skæreplaner [15] .

Den stereografiske projektion i argumentet fra Miller et al. kan undgås ved at betragte den mindste cirkel, der indeholder en konstant brøkdel af diskcentre, og derefter udvide med en mængde valgt ensartet i intervallet [1,2]. Det er let at vise, som i Millers, at skiverne krydset af en sådan cirkel danner en regulær separator, og så vil den matematiske forventning om antallet af skæringspunkter give det rigtige resultat. Sandt nok vil de resulterende konstanter være noget værre [16] .

Spektral partitionering

Spektral klyngemetoder , hvor grafens hjørnepunkter er grupperet efter egenværdikoordinaterne for matricer opnået fra grafen, har længe været brugt som heuristiske metoder til at løse grafopdelingsproblemer for ikke-plane grafer [17] [18] . Som Shpilman og Teng [19] har vist , kan spektral clustering også bruges til alternativt at bevise en svækket form af planar partitionssætningen anvendt på plane grafer med afgrænset toppunktsgrad. I deres metode er hjørnerne af en given plan graf sorteret efter den anden koordinat af egenvektorerne for Kirchhoff-matricen i grafen, og denne rækkefølge opdeles i et punkt, der minimerer forholdet mellem antallet af fjernede kanter og antallet af fjernede kanter. hjørner af den mindre del af skillevæggen. Som de viste, har enhver plan graf med en afgrænset grad af hjørner en partition, hvor dette forhold er O(1/√ n ). Selvom denne partition måske ikke er afbalanceret, vil gentagelse af partitionen af ​​den største af de to dele og sammenlægning af de opnåede snit ved hver iteration i sidste ende resultere i en afbalanceret partition med O(√ n ) kanter. Endespidserne af disse kanter danner en separator af størrelse (√ n ).

Ribbeadskillere

En variant af plannedbrydningssætningen taler om kantseparatorer , små sæt kanter, der danner et snit mellem to delmængder A og B af hjørnerne af en graf. De to sæt, A og B , skal højst have en størrelse, der er en konstant brøkdel af antallet n af toppunkter i grafen (normalt kræves det, at begge sæt ikke er større end 2 n /3), og hvert toppunkt på grafen tilhører kun til A eller B. Separatoren består af kanter, der har den ene ende i A og den anden ende i B. Kantseparatorens størrelsesgrænser afhænger både af graden af ​​grafens toppunkter og antallet af toppunkter i grafen - plane grafer, hvor et toppunkt har graden n  − 1, hvor hjul og stjerner falder , har ikke en separator med en sublineær antal kanter, da enhver kantadskiller bør omfatte alle kanter, der forbinder et højgrads vertex til spidser på den anden side af snittet. Imidlertid har enhver plan graf med maksimal grad Δ en kantseparator af størrelsen O(√(Δ n )) [20]

En simpel cyklusseparator i den dobbelte graf af en plan graf danner en kantseparator af den originale graf [6] [9] . Anvendelse af den simple cyklusseparatorsætning af Gacit og Miller [9] på den dobbelte graf af en given plan graf styrker O(√(Δ n )) estimatet for kantseparatorstørrelsen, da det viser, at enhver plan graf har en kantseparator hvis størrelse er proportional med den euklidiske norm for vektorens toppunktsgrader i grafen.

Papadimitrou og Sideri [21] beskrev en polynomiel-tidsalgoritme til at finde en kantseparator, der opdeler en graf G i to undergrafer af samme størrelse, hvis G er en genereret undergraf af en gittergraf uden huller eller med et konstant antal huller. Men de formodede, at problemet er NP-komplet for tilfælde af vilkårlige plane grafer, og viste, at kompleksiteten af ​​problemet for gittergrafer med et vilkårligt antal huller er den samme som for vilkårlige plane grafer.

Nedre grænser

I gittergrafen √ n  × √ n kan mængden S indeholdende s  < √ n punkter omgive en delmængde på højst s ( s  − 1)/2 punkter af gitteret, og maksimum opnås ved at placere S på diagonalen linje tættere på hjørnet af gitteret. For at danne en separator, der adskiller mindst n /3 punkter fra gitteret, skal s have en størrelse på mindst √(2 n /3), hvilket er omkring 0,82√ n .

Der er plane grafer med n toppunkter (for vilkårligt store værdier af n ), således at for enhver separator S , der opdeler den resterende graf i undergrafer med højst 2n /3 toppunkter, har S mindst √(4π√3)√ n hjørner, cirka 1,56√ n [2] . Konstruktionen bruger en tilnærmelse af en kugle ved et konveks polyeder ved at erstatte hver side af polyederet med et trekantet mesh. Den isoperimetriske sætning påføres derefter på overfladen af ​​en kugle.

Separatorhierarkier

Separatorer kan kombineres til et plant grafseparatorhierarki , en rekursiv dekomponering til mindre grafer. Separatorhierarkiet kan repræsenteres som et binært træ , hvor roden repræsenterer selve grafen, og de to underordnede noder af roden er rødderne af de genererede undergrafer af delmængder A og B i det rekursivt konstruerede separatorhierarki.

Hierarkiet af separatorer af denne type danner grundlaget for en trænedbrydning af en given graf, hvor det sæt af hjørner, der er knyttet til en træknude, er foreningen af ​​separatorer på stien fra denne knude til træets rod. Da størrelserne af graferne falder med en konstant faktor på hvert niveau i træet, falder de øvre grænser for størrelsen af ​​separatorerne også med en konstant faktor på hvert niveau, således at størrelserne af separatorerne langs disse stier summeres eksponentielt til O(√ n ). Det vil sige, at den således dannede separator har bredden O(√ n ), og denne kan bruges til at vise, at enhver plan graf har træbredden O(√ n ).

Opbygning af et separatorhierarki direkte ved at krydse det binære træ fra top til bund og anvende en lineær-tidsalgoritme til at finde en plan separator til hver af de genererede undergrafer, der er knyttet til hver knude i det binære træ, vil tage total tid O( n  log  n ) . Det er dog muligt at opbygge hele separatorhierarkiet i lineær tid, hvis vi bruger Lipton-Tarjans breddefibreringstilgang og anvender passende datastrukturer til at implementere hvert partitioneringstrin i sublineær tid [22] .

Hvis vi danner hierarkier baseret ikke på separatorer, men på afbrydelser, hvor to underordnede hjørner bliver rødder til den rekursive konstruktion af separatorhierarkier for to undergrafer G 1 og G 2 af adskillelsen af ​​en given graf, så danner den komplette struktur en dekomponering af grafen i grene , og ikke en trænedbrydning. Bredden af ​​enhver opdeling i denne dekomponering er igen afgrænset af summen af ​​størrelserne af separatorerne på stien fra en hvilken som helst knude til roden af ​​hierarkiet, således at enhver således opnået dekomponering har bredde O(√ n ) og en hvilken som helst plan graf har grenbredde O(√ n ). Selvom mange andre relaterede grafopdelingsproblemer er NP-komplette selv for plane grafer, er det muligt at finde en dekomponering af en plan graf til grene med minimumsbredde i polynomiel tid [23] .

Ved at anvende Alon, Seymour og Thomas [7] metoder mere direkte til at konstruere en grafnedbrydning til grene, viste Fomin og Tilikos [24] , at enhver plan graf har en forgreningsbredde, der ikke overstiger 2,12√ n , det vil sige med samme konstant som for partitioneringssætningen af ​​Alon Alon, Seymour og Thomas ved simple cyklusseparatorer. Da træbredden af ​​enhver graf højst er 3/2 af grenbredden, viser dette også, at plane grafer har en træbredde på højst 3,18√ n .

Andre klasser af grafer

Nogle sparsomme grafer har ikke sublineære størrelsesseparatorer - i en ekspander efterlader fjernelse af en konstant brøkdel af hjørner en forbundet komponent [4] [25] .

Den måske tidligste partitioneringssætning er Jordans resultat [26] om, at ethvert træ kan opdeles i to undertræer med højst n /2 toppunkter i hver ved at fjerne et enkelt toppunkt [10] . Især toppunktet, der minimerer størrelsen af ​​den maksimale komponent, har denne egenskab. Ved at anvende den samme teknik til trænedbrydningen af ​​en vilkårlig graf, kan det vises, at enhver graf har en separator med en størrelse, der ikke overstiger dens træbredde .

Hvis grafen G ikke er plan, men kan indlejres i en overflade af slægten g , så har den en separator med O(( gn ) 1/2 ) hjørner. Gilbert, Hutchinson og Tarjan [27] beviste dette ved at bruge en tilgang tæt på Lipton og Tarjans [4] . De grupperer grafens hjørner efter bredde-første søgeniveauer og finder to niveauer, hvis fjernelse efterlader højst én stor komponent bestående af et lille antal niveauer. Denne resterende komponent kan gøres plan ved at fjerne et antal bredde-først søgestier proportionalt med grafens slægt, hvorefter Lipton-Tarjan metoden kan anvendes på den resterende plane graf. Resultatet opnås ved omhyggeligt at balancere størrelsen af ​​de fjernede to niveauer og antallet af niveauer mellem dem. Givet en grafindlejring kan dens separator findes i lineær tid . Grafer af slægten g har separatorer af størrelsen O(( g Δ n ) 1/2 ) [28] .

Grafer af afgrænset slægt danner et eksempel på en familie af grafer, der er lukket under driften af ​​at tage mindreårige , og partitionsteoremer gælder for vilkårlige familier af grafer, der er lukket under at tage en mindreårig. Især hvis en familie af grafer har en forbudt minor med h toppunkter, så har den en separator med O( h √ n ) toppunkter, og en sådan separator kan findes i O( n 1 + ε ) tid for enhver ε > 0 [29]

Metoden til separator-cykler for Miller, Teng, Thurston og Vavasis [10] er generaliseret til skæringsgraferne for ethvert system af d - dimensionelle kugler, som har den egenskab, at ethvert punkt på overfladen højst er dækket af kugler en eller anden konstant antal k gange, for grafer k - nærmeste naboer i rummet af dimension d [10] , og for grafer, der opstår i finite element-gitter [30] . Sfæriske separatorer konstrueret på denne måde opdeler inputgrafen i undergrafer med højst n ( d + 1)/( d + 2) hjørner. Størrelsen af ​​separatorer for grafer af k - fold overlappende kugler og grafer for k -nærmeste naboer er O( k 1/ d n 1 − 1/ d ) [10] .

Ansøgninger

Divide and Conquer Algoritmer

Separator-partitioner kan bruges til at bygge effektive " Del og erob "-algoritmer til løsning af problemer på plane grafer. Et eksempel på et problem, der kan løses med denne tilgang, er at finde den korteste cyklus i en vægtet plan rettet graf. Du kan gøre det sådan her:

Tiden for to rekursive kald for A og B i denne algoritme er domineret af O(√ n ) køretiden for Dijkstras algoritme, så denne algoritme finder den korteste cyklus i O( n 3/2  log  n ) tid.

En hurtigere algoritme til det samme problem med at finde den korteste cyklus, der løber i tiden O( n  log 3 n ), blev givet af Wolf-Nielsen [31] . Hans algoritme bruger den samme del-og-hersk-struktur baseret på separatorer, men bruger simple cyklusseparatorer i stedet for vilkårlige separatorer, således at hjørnerne af sættet S hører til den samme flade (for den indre graf og for den ydre graf med respekt til separatoren). Den erstatter derefter O(√ n ) individuelle kald til Dijkstras algoritme med mere sofistikerede algoritmer til at finde korteste veje fra alle hjørner på en enkelt side af en plan graf og kombinere afstande fra to undergrafer. For vægtede, men urettede plane grafer, svarer den korteste cyklus til det mindste snit i den dobbelte graf og kan findes i O( n  log log  n ) tid [32] , og den korteste cyklus i en vægtet cyklus urettet plan graf (dets omkreds ) kan findes i tiden O( n ) [33] . (Den hurtigere algoritme for uvægtede grafer er dog ikke baseret på partitionssætningen.)

Frederickson foreslog i 1986 en anden hurtig algoritme til den korteste vej fra en enkelt kilde ved at bruge partitioneringssætningen for plane grafer [34] . Algoritmen er en forbedring af Dijkstras iterative søgning på en nøje udvalgt undergruppe af hjørner. Denne version kører i O( n √(log n )) tid på en graf med n toppunkter. Separatorer bruges til at finde opdelingen af ​​en graf, det vil sige dens opdeling i to eller flere delmængder, kaldet områder. En knude siges at være indeholdt i en region, hvis en kant af regionen falder ind i knudepunktet. En knude, der er indeholdt i mere end ét område, kaldes grænseknuden for de områder, der indeholder den. Metoden bruger begrebet en r -division af en graf med n noder, hvilket svarer til at opdele grafen i O( n / r )-områder, som hver indeholder O( r )-knuder, inklusive O(√r ) -grænsenoder . Frederickson viste, at r -divisionen kan findes i O( n log n ) tid ved rekursivt at anvende partitionssætningen.

Oversigt over algoritmen til løsning af problemet.

1. Indledende forberedelse . Vi opdeler grafen i nøje udvalgte delmængder af toppunkter og finder de korteste veje mellem alle par af toppunkter i disse delmængder, hvor de mellemliggende hjørner af stien ikke tilhører delmængden. I denne fase er det nødvendigt at transformere den plane graf G 0   til G , som ikke har nogen toppunkter med grad større end 3. Fra Euler- formlen vil antallet af toppunkter i den resulterende graf være n ≤ 6 n 0  −12, hvor n 0   er antallet af toppunkter i grafen G 0  . Denne fase giver også følgende egenskaber for passende r- delinger. En passende r -division af en plan graf er en r -division sådan, at

2. Søg

Henzinger et al udvidede Fredericksons r -divisionsteknik for algoritmen til at finde den korteste vej fra en enkelt kilde i plane grafer med ikke-negative kantlængder og foreslog en lineær tidsalgoritme [35] . Deres metode generaliserer forestillingen om en Fredrekson-partition for en graf, så nu en ( r , s )-partition af en graf med n noder bliver en partition i O( n / r )-områder, der hver indeholder r {O(1) }   noder og højst s grænseknuder. Hvis ( r , s )-partitionen gentages sekventielt for at opdele i mindre områder, kaldes dette en rekursiv partition. Algoritmen bruger ca. log* n divisionsniveauer. Rekursiv division er repræsenteret af et rodfæstet træ, hvis blade er mærket med forskellige kanter af grafen G. Træets rod repræsenterer det område, der består af hele grafen G , rodens børn repræsenterer de underområder, som området er opdelt i. Hvert blad repræsenterer præcis én kant.

Nested dissection  er en separator-baseret variation af divide-and-conquer-tilgangen til Gauss-elimineringsmetoden til at løse sparsomme symmetriske systemer af lineære algebraiske ligninger med en plan grafstruktur, såsom opstår i finite element-metoden . Metoden anvender søgningen efter en separator til ligningsbeskrivelsesgrafen, idet man rekursivt ekskluderer variabler i to underopgaver adskilt fra hinanden af ​​en separator, og ekskluderer derefter variablerne i separatoren [36] . Belægningen af ​​denne metode (antallet af ikke-nul-koefficienter for den resulterende Cholesky-udvidelse for en matrix) er O( n  log  n ) [37] [38] , hvilket gør det muligt for denne metode at konkurrere med iterative metoder for de samme problemer [ 36] .

Klein, Moses og Weimann [39] foreslog en O( n log 2  n ) lineær hukommelsesalgoritme til at finde de korteste afstande fra s for alle noder i en rettet plan graf med positive og negative buelængder, der ikke indeholder negative cyklusser. Deres algoritme bruger plane grafseparatorer til at finde en Jordan-kurve C , der går gennem O(√ n ) noder (men ikke gennem buer), således at mellem n /3 og 2 n /3 noder er inde i (området afgrænset af den lukkede) kurve C . De knudepunkter, som kurven C passerer, er grænseknuder . Den originale graf G er opdelt i to undergrafer G 0   og G 1 , der afskærer den plane indlejring langs kurven C og duplikerer grænseknuderne. For i =0 og 1 ligger grænseknuderne i Gi i den   ene side af Fi  .

En oversigt over denne tilgang er givet nedenfor.

En vigtig del af denne algoritme er brugen af ​​funktionerne Pris og Reduceret Længde. For en rettet graf G med buelængder ι(•) er omkostningsfunktionen funktionen φ fra knudepunkterne i grafen G til de reelle tal . For en bue uv er den reducerede længde i forhold til φ ιφ( uv )=ι( uv ) + φ( u ) − φ( v ). En tilladt omkostningsfunktion er en funktion, der giver ikke-negative reducerede længder på alle buer af G . Det er nyttigt at konvertere et problem med den korteste vej, der har både positive og negative buelængder, til et problem med ikke-negative længder, hvilket gør det muligt at bruge Dijkstras algoritme.

Det separatorbaserede opdel-og-hersk-paradigme bruges også til at udvikle datastrukturer til dynamiske grafalgoritmer [40] [41] og punktlokalisering [42] , polygontrianguleringsalgoritmer [22] , korteste veje [ 43] [44] , til at konstruere nærmeste nabografer [45] og tilnærmelsesalgoritmer til at finde det maksimale uafhængige sæt på plane grafer [42] .

Præcis løsning af NP-hårde optimeringsproblemer

Når du bruger dynamisk programmering på trænedbrydning eller grennedbrydning til en plan graf, kan mange klasser af NP-hårde optimeringsproblemer løses eksponentielt i tid afhængig af √ n eller √ n  log  n . For eksempel er grænser af denne art kendt for at søge efter maksimale uafhængige sæt , Steiner-træer , Hamiltonske cyklusser og for at løse det rejsende sælgerproblem på plane grafer [46] . Lignende metoder ved hjælp af partitioneringssætninger for geometriske grafer kan bruges til at løse det euklidiske rejsende sælgerproblem og bygge et Steiner-træ inden for samme tidsgrænser [47] .

For parameteriserede problemer, der tillader parametrisk reduktion , der bevarer planaritet og reducerer inputfilen til en kerne med en størrelse, der afhænger lineært af parameteren, kan denne tilgang bruges til at konstruere fast-parametrisk løsbare algoritmer, hvis udførelsestid afhænger af polynomielt på størrelsen af ​​inputgrafen og eksponentielt i √ k , hvor k  er en parameter for algoritmen. For eksempel er runtime-grænser af denne art kendt for at finde toppunktsdæksler og dominerende sæt af størrelse k [48] [49] .

Approksimationsalgoritmer

Lipton og Tarjan [42] observerede, at partitionssætningen kan bruges til at udlede polynomie-tidstilnærmelsesskemaer for NP-hårde optimeringsproblemer på plane grafer, såsom at finde det maksimale uafhængige sæt . Især ved at afkorte separatorhierarkiet på et passende sted kan man finde en separator med størrelse O( n /√log  n ), hvis fjernelse opdeler grafen i undergrafer med størrelse c  log  n for enhver konstant c . Ved firefarvesætningen er der et uafhængigt sæt af størrelse mindst n / 4 , så de fjernede noder danner en lille brøkdel af det maksimale uafhængige sæt, og de maksimale uafhængige mængder i de resterende undergrafer kan findes uafhængigt i tidseksponentielt afhængige på deres størrelse. Ved at kombinere denne tilgang med de lineære-tidsmetoder til at konstruere et separatorhierarki [22] med et tabelopslag for at reducere tiden for søgning efter uafhængige mængder i isomorfe undergrafer, kan man konstruere uafhængige mængder, der afviger fra optimale med en faktor 1 − O(1/√log  n ) i lineær tid. Men for garanteret effektivitet endnu tættere på 1 end denne faktor giver Bakers ( Baker 1994 ) senere tilgang (baseret på trænedbrydning frem for plane separatorer) et bedre kompromis mellem tid og tilnærmelseskvalitet.

Lignende tilnærmelsesskemaer baseret på konstruktion af separatorer bruges til at tilnærme andre vanskelige problemer, såsom toppunktsdækningsproblemet [50] [51] . Arora, Grigni, Karger, Klein og Voloshin [52] brugte separatorer på en anden måde til at tilnærme det rejsende sælgerproblem for den korteste vejmetrik på vægtede plane grafer. Deres algoritme bruger dynamisk programmering til at finde den korteste vej, der på hvert niveau i separatorhierarkiet krydser separatoren et begrænset antal gange. De viste, at når grænsen for antallet af kryds øges, har de ruter, der er konstrueret på denne måde, en længde, der tilnærmer den optimale rute.

Grafkomprimering

Separatorer bruges som en del af datakomprimeringsalgoritmer til at repræsentere plane grafer og andre separerbare grafer ved hjælp af et lille antal bits. Hovedprincippet i disse algoritmer er at vælge et tal k og opdele den givne plane graf ved hjælp af separatorer i O( n / k ) undergrafer af størrelse på højst k , med O( n /√ k ) hjørner i separatorerne. Med et passende valg af k (maksimalt proportionalt med logaritmen af ​​n ), er antallet af ikke-isomorfe plane subgrafer med k toppunkter væsentligt mindre end antallet af subgrafer i dekomponeringen, så graferne kan komprimeres ved at konstruere en tabel over alle mulige ikke-isomorfe undergrafer og repræsenterer hver undergraf i dekomponeringen med et indeks i tabellen. Resten af ​​grafen dannet af hjørnerne af separatoren kan repræsenteres eksplicit eller med en rekursiv version af den samme datastruktur. Ved hjælp af denne metode kan plane grafer og mere begrænsede familier af plane grafer kodes ved hjælp af det optimale antal bits (med hensyn til informationsteori ) - hvis der er grafer P n med n toppunkter i en graffamilie, så er en individuel graf fra familie kan repræsenteres ved brug af kun (1 + o( n ))log 2 P n bits [53] . Man kan også opbygge visninger af denne type, hvor man kan kontrollere tilstødelse af toppunkter, bestemme graden af ​​et toppunkt og liste toppunktsnaboer i konstant tid (pr. forespørgsel), ved at udvide undergraftabellen med yderligere information med data svarende til forespørgsler [54] [55] .

Universelle grafer

En universel graf for en graffamilie F  er en graf, der indeholder et hvilket som helst element i familien F som en undergraf. Separatorer kan bruges til at vise, at n-vertex plane grafer har en universel graf med n toppunkter og O( n 3/2 ) kanter [56] .

Konstruktionen bruger en stærkere form af partitionssætningen, hvor størrelsen af ​​de tre delmængder af toppunkter i partitionen ikke afhænger af grafens struktur - der er et tal c , hvis værdi er en konstant faktor større end √ n , sådan at hjørnerne af enhver plan graf med n toppunkter kan opdeles i delmængder A , S og B uden kanter fra A til B og med dimensioner | S | =  c , | A | = | b | = ( n  -  c )/2. Dette kan vises ved at anvende den sædvanlige form af partitioneringssætningen gentagne gange på de resulterende partitioner af grafen, indtil alle komponenter af partitionen er samlet i to delmængder, som hver er mindre end n /2 hjørnepunkter i størrelse, og derefter overføre hjørner fra disse delmængder til separatoren, indtil den ikke vil have den givne størrelse.

Nu kan denne sætning bruges til at opnå et separatorhierarki for en plan graf med n toppunkter, som igen er uafhængig af grafens struktur - trænedbrydningen opnået fra dette hierarki er O(√ n ) bred og kan bruges til evt. plan graf. Mættet af alle par af toppunkter i denne trænedbrydning, hvor hver af de to toppunkter tilhører en fælles knude for trænedbrydningen, danner en trivielt perfekt graf med O( n 3/2 ) toppunkter, som indeholder en hvilken som helst plan graf med n hjørner som en undergraf. En lignende konstruktion viser, at plane grafer af afgrænset grad har universelle grafer med O( n  log  n ) kanter, hvor konstanten skjult i O- notationen afhænger af grafens grad. Enhver universel graf for plane grafer (eller endda for træer med ubegrænset grad) skal have Ω( n  log  n ) kanter, men det er stadig ukendt, om denne nedre grænse eller O( n 3/2 ) øvre grænse er skarp for universelle grafer for vilkårlige plane grafer [56] .

Se også

Noter

  1. ↑ 1 2 Alon, Seymour, Thomas, 1990 .
  2. ↑ 1 2 3 Djidjev, 1982 .
  3. ↑ George, 1973 . I stedet for at bruge rækker og kolonner som separator til at opdele grafen, bruger George deres forening og opdeler grafen i fire dele.
  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 ) beviste dette resultat for 2-forbundne plane grafer, mens Diks, Djidjev, Sýkora, Vrt'o (1993 ) udvidede resultatet til alle plane 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. ↑ Jordan, 1869 .
  27. ↑ Gilbert, Hutchinson, Tarjan, 1984 .
  28. ↑ Sykora, Vrt'o, 1993 .
  29. ↑ Kawarabayashi, Reed, 2010 . Tidligere arbejde med separatorer af mindre lukkede familier - 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 , s. 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