Šířka stopy

V teorii grafů je rozklad cesty grafu G  neformálně znázorněním grafu G jako „ztluštělé“ cesty [1] a šířka cesty grafu G  je číslo, které měří, kolik grafu G bylo zahuštěný. Formálněji je rozklad cesty posloupností vrcholů podmnožiny grafu G tak, že koncové vrcholy každé hrany se objeví v jedné z podmnožin a každý vrchol patří (alespoň) jedné z množin [2] , a šířka cesty je o jednu menší než velikost největšího souboru v takovém rozkladu. Šířka cesty je také známá jako tloušťka intervalu (o jednu menší než je velikost největší kliky intervalového supergrafu grafu G ), hodnota separace vrcholů nebo vyhledávací číslo vrcholu [3] [4] .

Šířka cesty a rozklad cesty jsou velmi podobné šířce stromu a rozkladu stromu . Hrají klíčovou roli v teorii grafových minorit  - rodiny grafů, které jsou uzavřeny pod graph minors a nezahrnují všechny lesy , lze charakterizovat jako s omezenou šířkou cesty [2] , a "víry", které vznikají v obecné strukturální teorie rodin grafů uzavřených s ohledem na nezletilé, mají omezenou šířku cesty [5] . Grafy šířky cesty a ohraničené šířky cesty mají aplikace v inženýrství VLSI , vizualizaci grafů a výpočetní lingvistice .

Problém hledání šířky cesty libovolných grafů je NP-těžký . Navíc i problém přesné aproximace šířky cesty je NP-těžký [6] [7] . Tento problém je však pevně-parametricky řešitelný  — testování, zda má graf šířku cesty k , lze řešit v čase, který je lineární ve velikosti grafu, ale superexponenciální v k [8] Navíc pro některé speciální třídy grafů, jako např. stromy , šířku cesty lze vypočítat v polynomiálním čase nezávisle na k [9] [10] . Mnoho problémů v teorii grafů lze efektivně vyřešit na grafech s omezenou šířkou cesty pomocí dynamického programování na cestě rozkladu grafu [11] . Stromovou dekompozici lze také použít k odhadu kapacitní složitosti algoritmů dynamického programování na grafech s omezenou šířkou stromu [12] .

Definice

Robertson a Seymour [2] definovali v první slavné sérii prací o grafových mollových grafech dráhový rozklad grafu G jako posloupnost podmnožin X i vrcholů grafu G se dvěma vlastnostmi:

  1. Pro každou hranu G existuje i takové, že oba koncové body hrany patří do podmnožiny X i
  2. Pro libovolné tři indexy i ≤ j ≤ k , X i ∩ X k ⊆ X j .

Druhá z těchto dvou vlastností je ekvivalentní požadavku, aby podmnožiny obsahující libovolný vrchol tvořily souvislou podsekvenci celé sekvence. V jazyce pozdějších sérií Robertsona a Seymoura o menších grafech je rozklad cesty stromový rozklad ( X , T ), ve kterém je základním rozkladovým stromem T cesta .

Šířka rozkladu cesty je definována stejným způsobem jako u stromového rozkladu jako max i  | X i | − 1 a šířka dráhy grafu G je rovna minimální šířce všech rozkladů dráhy grafu G . Odečtení jedné od velikosti X i v této definici má malý vliv na většinu aplikací šířky cesty, ale činí šířku cesty rovnou jedné.

Alternativní popisy

Jak píše Bodlaender [3] , pathwidth lze popsat mnoha ekvivalentními způsoby.

Sekvence lepení

Stromový rozklad lze popsat jako posloupnost grafů G i , které jsou slepeny identifikací párů vrcholů v sousedních grafech posloupnosti a výsledkem tohoto slepení je vytvořen graf G . Jako grafy G i můžeme vzít vygenerované podgrafy množin X i v první definici rozkladu cest se slepením vrcholů v sousedních vygenerovaných podgrafech, pokud jsou tyto vrcholy generovány stejným vrcholem z G . V jiném směru je možné vzít X i jako vrcholové množiny grafů Gi . Šířka rozkladu stromu je pak o jednu menší než maximální počet vrcholů v jednom z grafů G i [2] .

Tloušťka intervalu

Šířka cesty jakéhokoli grafu G je o jednu menší než nejmenší klikové číslo intervalového grafu obsahujícího G jako podgraf [14] . To znamená, že pro jakýkoli stromový rozklad grafu G lze najít intervalový nadgraf a pro jakýkoli intervalový nadgraf G lze nalézt stromový rozklad grafu G , jehož šířka rozkladu je o jednu menší než klikové číslo intervalového grafu. .

V jednom směru předpokládejme, že je dán stromový rozklad grafu G. Potom lze vrcholy rozkladu reprezentovat jako body na přímce (v pořadí, ve kterém vstupují do cesty) a reprezentovat každý vrchol v jako uzavřený interval mající tyto body jako koncové body. Nechť ( X 1 , . . . , X r ) je například dráhový rozklad grafu G , bodů na přímce [1, . . . , r], pak reprezentace vrcholu v je interval . Potom stromový rozklad vrcholů obsahujících v odpovídá reprezentaci (tj. koncovým bodům) intervalu pro v . Intervalový průsečíkový graf vytvořený z vrcholů G je intervalový graf obsahující G jako podgraf. Jeho maximální kliky jsou dány množinou intervalů obsahujících reprezentující body a jejich největší velikost kliky je o jednu větší než šířka cesty grafu G .

V opačném směru, je-li G podgrafem intervalového grafu s číslem kliky p  + 1, pak G má stromový rozklad o šířce p , jehož vrcholy jsou dány maximálními klikami intervalového grafu. Například intervalový graf zobrazený s jeho intervalovou reprezentací na obrázku má stromový rozklad s pěti vrcholy odpovídajícími pěti maximálním klikám ABC , ACD , CDE , CDF a FG . Velikost maximální kliky je tři a šířka tohoto rozkladu stromu je dvě.

Tato ekvivalence mezi šířkou dráhy a tloušťkou intervalu je blízká analogie k ekvivalenci mezi šířkou stromu a minimálním počtem kliky (mínus jedna) chordálního grafu , jehož je daný graf podgrafem. Intervalové grafy jsou speciálním případem tětivových grafů a tětivové grafy mohou být reprezentovány jako grafy průsečíků podstromů obecných stromů, což zobecňuje přístup, ve kterém jsou intervalové grafy interpretovány jako grafy průsečíků dílčích cest.

Částka rozdělení vertexu

Předpokládejme, že vrcholy grafu G jsou lineárně uspořádány . Pak velikost rozdělení vrcholu G je nejmenší číslo s takové, že pro každý vrchol v předchází v v uspořádání nejvýše s vrcholů, které mají ve svém okolí v nebo jeden z následujících vrcholů. Hodnota rozdělení vrcholu grafu G je minimální hodnota rozdělení vrcholu jakéhokoli lineárního libovolného lineárního uspořádání grafu G . Hodnota vertex split byla zavedena Ellisem, Sudboroughem a Turnerem [15] a je rovna šířce dráhy grafu G [16] [17] . Vyplývá to z dříve zmíněné ekvivalence intervalových grafů a klikových čísel - je-li G podgraf intervalového grafu I , znázorněného (jako na obrázku) tak, že všechny konce intervalů jsou různé, pak pořadí levé konce intervalů grafu I mají hodnotu separace vrcholů o jednu menší než čísla klik sloupce I . V opačném směru, z lineárního uspořádání G , lze získat intervalovou reprezentaci, ve které levý koncový bod intervalu pro vrchol v je pozice v uspořádání a pravý koncový bod je pozice posledního souseda v v objednání.

Číslo hledání vrcholu

Nejlepší hra na grafu je typ hry s vyhýbáním se pronásledování, ve které více pronásledovatelů spolupracuje na vypátrání uprchlíka skrývajícího se v grafu. Pronásledovatelé jsou umístěni ve vrcholech grafu, zatímco uprchlík může být umístěn na libovolném okraji grafu, jeho umístění a pohyby nejsou pro pronásledovatele viditelné. Během dalšího tahu se někteří (nebo všichni) pronásledovatelé mohou pohybovat (libovolně, ne nutně podél hran) z jednoho vrcholu do druhého a uprchlík se pak pohybuje po libovolné cestě na grafu, ale nemůže projít vrcholy obsazenými pronásledovatelé. Uprchlík je chycen, když oba konce oblouku, na kterém je, jsou obsazeny pronásledovateli. Počet prohledávaných vrcholů grafu je minimální počet pronásledovatelů nezbytný k zaručení dopadení uprchlíka bez ohledu na jeho chování. Jak ukázali Kyrouzis a Panadimitriou [18] , číslo pro vyhledávání vrcholu grafu se rovná jeho tloušťce intervalu. Optimální strategií pro pronásledovatele jsou tahy, ve kterých pronásledovatelé postupně tvoří oddělující množiny lineárního uspořádání s minimálním odstupem vrcholů.

Hranice

Každý graf s n vrcholy a šířkou cesty k má nejvýše k ( n − k + ( k − 1)/2)) hran a maximální grafy s šířkou cesty k (grafy, ke kterým nelze přidat hranu bez zvětšení cesty šířka) mít přesnost je počet hran. Maximální graf s šířkou cesty k musí být buď k -cesta nebo k -housenka, tzn. jeden ze dvou speciálních druhů k - stromu. K - strom je akordický graf s přesně n − k maximálními klikami , z nichž každý obsahuje k + 1 vrcholů. V k - stromu, který sám není ( k + 1)-klikou , každá maximální klika buď rozděluje graf na dvě nebo více složek, nebo obsahuje jeden vrchol listu, vrchol, který patří pouze jedné maximální klikě. K -cesta je k -strom s nejvýše dvěma listy a k -housenka je k - strom, který lze rozdělit na k -cestu a sadu k -listů, z nichž každý sousedí s oddělovačem k-klik. z cesty k . Zejména maximální grafy šířky cesty jedna jsou přesně housenkové grafy [19] .

Vzhledem k tomu, že rozklady cest jsou speciální případy rozkladů stromů, šířka cesty jakéhokoli grafu je větší nebo rovna šířce stromu . Šířka cesty je také menší nebo rovna šířce řezu, minimálnímu počtu hran, které protínají jakýkoli řez mezi vrcholy s nižším indexem a vyšším indexem v optimálním lineárním uspořádání vrcholů grafu. Vyplývá to z toho, že velikost rozdělení vrcholu, počet vrcholů s nižším indexem se sousedy s vyšším indexem, není větší než počet řezných hran [20] [21] . Ze stejného důvodu šířka řezu nepřesahuje šířku cesty vynásobenou maximálním stupněm vrcholů v daném grafu [22] [23] .

Každý les s n vrcholy má šířku cesty O(log  n ) [24] [25] [26] . U lesa lze vždy najít konstantní počet vrcholů, jejichž odstraněním vznikne les, který lze rozdělit na dva menší lesy s maximálně 2 n /3 vrcholy v každém z těchto lesů. Lineární uspořádání vytvořené rekurzivní aplikací takového rozdělení má logaritmické vyhledávací číslo pro vrcholy. Stejná technika aplikovaná na stromový rozklad grafu ukazuje, že pokud je šířka stromu n - vrcholového grafu G t , pak šířka cesty G je O( t  log  n ) [27] [28] . Protože vnější rovinné grafy , paralelní sériové grafy a Halinovy ​​grafy mají všechny ohraničenou šířku stromu, mají všechny maximální logaritmickou šířku cesty.

Kromě toho, že souvisí se šířkou stromu, souvisí šířka cesty s šířkou kliknutí a šířkou řezu prostřednictvím spojnicových grafů . Spojnicový graf L ( G ) grafu G má vrchol pro každou hranu G a dva vrcholy v L ( G ) sousedí, pokud odpovídající dvě hrany mají G společných koncových bodů. Jakákoli rodina grafů má omezenou šířku cesty právě tehdy, když její čárové grafy mají ohraničenou šířku lineární kliky, kde šířka lineární kliky nahrazuje operaci sjednocení v definici šířky kliky operací připojení jediného nového vrcholu [29] . Pokud má souvislý graf se třemi nebo více vrcholy maximální stupeň 3, jeho šířka řezu se rovná rozdělení vrcholu jeho spojnicového grafu [30] .

V libovolném rovinném grafu je šířka dráhy v nejhorším případě úměrná druhé odmocnině počtu vrcholů [31] . Jedním ze způsobů, jak najít rozklad cesty s touto šířkou, je (podobný rozkladu cesty logaritmické šířky popsané výše) použít větu o rovinném rozdělení k nalezení množiny O(√ n ) vrcholů, jejichž odstranění rozdělí graf na dva podgrafy s a maximálně 2 n /3 vrcholů v každém a spojují rozklady cest konstruované rekurzivně pro tyto dva podgrafy. Stejná technika platí pro jakoukoli třídu grafů, pro které platí podobná věta o rozdělení [32] . Protože každá rodina grafů uzavřená za nezletilé, jako v případě rovinných grafů, má dělící množinu vrcholů o velikosti O(√ n ) [33] , vyplývá, že šířka grafů v jakékoli pevné rodině uzavřené pod nezletilými je opět O(√ n ). U některých tříd rovinných grafů musí šířka dráhy grafu a šířka jeho duálního grafu ležet v intervalu, jehož hranice závisí lineárně na hodnotách – takové hranice jsou známé pro dvojitě spojené vnější rovinné grafy [34] [35] a pro polytop grafy [36] [37] . U dvojitě spojených rovinných grafů je šířka dráhy duálního grafu menší než šířka spojnicového grafu [38] . Zůstává otevřenou otázkou, zda šířky dráhy planárního grafu a jeho duálu jsou pro zbytek případů vždy v lineárních hranicích.

U některých tříd grafů bylo prokázáno, že pathwidth a treewidth jsou si vždy rovny - to platí pro cography [39] , permutační grafy [40] , doplňky grafů srovnatelnosti [41] a grafy srovnatelnosti intervalových řádů [42] .

Nevyřešené problémy v matematice : Jaká je maximální šířka cesty kubického grafu s vrcholy?

V jakémkoli kubickém grafu nebo obecněji jakémkoli grafu s maximálním vrcholovým stupněm 3 je šířka cesty nejvýše n /6 + o( n ), kde n je počet vrcholů v grafu. Existují kubické grafy se šířkou dráhy 0,082 n , ale není známo, jak tuto mezeru uzavřít mezi dolní hranicí a horní hranicí n /6 [43] .

Výpočetní dekompozice cest

Určení, zda šířka dráhy překračuje danou hodnotu k pro daný graf, je NP-úplné , pokud k je vstup [6] . Nejznámější časové hranice ( v nejhorším případě ) pro výpočet šířky dráhy libovolného grafu s n vrcholy jsou O(2 n  n c ) pro nějakou konstantu c [44] . Je však známo, že některé algoritmy rozkladu cesty jsou účinnější, pokud je šířka cesty malá, pokud je třída vstupního grafu omezena nebo pokud je třeba šířku cesty aproximovat.

Pevně ​​parametrická rozlišitelnost

Šířka cesty je pevně-parametricky rozlišitelná — pro libovolnou konstantu k lze zkontrolovat, zda šířka dráhy překračuje k , a pokud ne, najít rozklad cesty na šířku k v lineárním čase [8] . Obecně tyto algoritmy fungují ve dvou fázích. První krok využívá předpokladu, že graf má šířku cesty k k nalezení rozkladu cesty nebo stromové dekompozice. Tento rozklad není optimální, ale jeho šířka může být omezena funkcí k . Ve druhé fázi je použit dynamický programovací algoritmus k nalezení optimálního rozkladu. Časové limity pro známé algoritmy tohoto typu jsou však exponenciální v k 2 a nejsou prakticky zajímavé, snad s výjimkou malých hodnot k [45] . Pro případ k  = 2 uvedl Fleiter lineární časový algoritmus založený na strukturálním rozkladu grafů s šířkou dráhy 2 [46] .

Speciální třídy grafů

Bodlaender [9] podal přehled o složitosti úloh šířky cesty na různých speciálních třídách grafů. Určení, zda šířka dráhy grafu G přesahuje k , zůstává NP-úplným problémem, pokud G vezmeme z grafů omezeného stupně [47] , rovinných grafů [47] , rovinných grafů omezeného stupně [47] , tětivových grafů [48] , chordální domino [49] , doplňky grafů srovnatelnosti [41] a bipartitní grafy zděděné vzdáleností [50] . To okamžitě znamená, že problém je také NP-úplný pro rodiny grafů obsahujících bipartitní grafy zděděné vzdáleností , včetně bipartitních grafů, chordálních bipartitních grafů, grafů zděděných vzdáleností a kruhových grafů [50] .

Šířku cesty však lze pro stromy a lesy vypočítat v lineárním čase [10] . Tuto hodnotu je možné vypočítat v polynomiálním čase pro grafy šířky ohraničeného stromu, které zahrnují paralelně-sekvenční grafy , vnější rovinné grafy a Halinovy ​​grafy [8] , stejně jako dělené grafy [51] [48] , doplňky akordických grafů [ 52] , permutační grafy [40] , kografy [39] , kruhové obloukové grafy [53] , grafy srovnatelnosti intervalového řádu [42] a samozřejmě samotné intervalové grafy , protože pro ně je šířka dráhy prostě o jednu menší než maximální pokrytí intervalu počet libovolného bodu v grafu zobrazení intervalu.

Aproximační algoritmy

NP-těžký problém je aproximace šířky dráhy grafu aditivní konstantou [7] . Nejznámější aproximační koeficient polynomiálních časových aproximačních algoritmů pro šířku dráhy je O((log  n ) 3/2 ) [54] . Rané algoritmy aproximace šířky cesty lze nalézt u Bodlaendera, Gilberta, Hafsteinssona, Kloxe [7] a Gooha [55] . Pro aproximaci omezených tříd grafů viz knihu Cloxe a Bodlaendera [51] .

Počítat nezletilé

Menší část grafu G je další graf vytvořený z G stažením hran, vymazáním hran a vrcholů. Graph minors mají hlubokou teorii, ve které některé důležité výsledky využívají šířku cesty.

Vyloučení lesa

Pokud je rodina F grafů uzavřena operací odebírání nezletilých (jakýkoli nezletilý člen rodiny F je obsažen také v F ), pak lze podle Robertsonovy–Seymourovy věty rodinu F charakterizovat jako grafy, které obsahovat nezletilé z X , kde X je konečná množina zakázaných nezletilých [56] . Například Wagnerova věta říká, že rovinné grafy jsou grafy, které neobsahují ani úplný graf K 5 ani úplný bipartitní graf K 3,3 jako vedlejší. V mnoha případech spolu vlastnosti F a vlastnosti X úzce souvisejí a první výsledek tohoto typu získali Robertson a Seymour [2] a dává do souvislosti existenci ohraničené šířky cesty s přítomností lesa v rodina zakázaných nezletilých. Konkrétněji definujeme rodinu F grafů jako mající omezenou šířku dráhy , pokud existuje konstanta p taková, že jakýkoli graf v F má šířku dráhy nejvýše p . Potom má uzavřená rodina F ohraničenou šířku cesty právě tehdy, když množina X zakázaných nezletilých pro F zahrnuje alespoň jeden les.

V jednom směru lze tento výsledek dokázat přímo – totiž, že pokud X neobsahuje alespoň jeden les, pak grafy bez X -minorů nemají ohraničenou šířku cesty. V tomto případě grafy bez X -minor zahrnují všechny lesy a zejména dokonalé binární stromy . Ale dokonalé binární stromy s 2k  + 1 úrovněmi mají šířku dráhy k , takže v tomto případě mají grafy bez X -minor neomezenou šířku dráhy. V opačném směru, pokud X obsahuje les s n vrcholy, pak X -minor-free grafy mají šířku cesty nejvýše n  − 2 [57] [58] [59] .

Odhady šířky koleje

Vlastnost s šířkou cesty nanejvýš p je sama o sobě vedlejší uzavřená vlastnost — pokud má G rozklad cesty s šířkou maximálně p , pak stejný rozklad cesty zůstane pravdivý, i když se odstraní jakákoli hrana z G . jako každý vrchol může být odstraněn z G a jeho rozkladu cesty bez zvětšení šířky. Kontrakce okraje může být také dokončena bez zvětšení šířky rozkladu sloučením dílčích drah představujících dva konce okraje, který se stahuje. Grafy s šířkou cesty nejvýše p lze tedy charakterizovat množinou X p zakázaných nezletilých [56] [16] [60] [61] .

Ačkoli X p nutně zahrnuje alespoň jeden les, není pravda, že všechny grafy v X p jsou lesy. Například X 1 se skládá ze dvou grafů, stromu se sedmi vrcholy a trojúhelníku K 3 . Množinu stromů v X p lze ale přesně popsat - to jsou přesně ty stromy, které lze sestavit ze tří stromů z X p  − 1 vytvořením nového kořene a jeho připojením hranami k libovolně zvoleným vrcholům menších stromů. Například strom se sedmi vrcholy v X 1 je vytvořen ze stromů se dvěma vrcholy (jedna hrana) z X 0 . Na základě této konstrukce lze ukázat, že počet zakázaných nezletilých v X p není menší než ( p !) 2 [16] [60] [61] . Byla vypočtena kompletní sada X 2 zakázaných nezletilých pro grafy se šířkou cesty 2. Tato sada obsahuje 110 různých grafů [62] .

Strukturální teorie

Věta o struktuře grafu pro rodiny menších uzavřených grafů uvádí, že pro jakoukoli rodinu F , ve které lze grafy rozložit na klikové součty, grafy, které lze vložit do ploch ohraničeného rodu , spolu s omezeným počtem vrcholů a vírů pro každý složka klikového součtu . Vrchol je vrchol, který sousedí se všemi vrcholy komponenty, a vír je graf šířky ohraničené cesty, který je přilepen k povrchu komponenty injekcí ohraničeného rodu. Cyklické pořadí vrcholů kolem plochy, ve které je vír vnořen, musí být kompatibilní se stromovým rozkladem víru v tom smyslu, že přerušení cyklu za účelem vytvoření lineárního uspořádání musí vést k uspořádání s omezeným množstvím oddělení vrcholů [ 5] . Tato teorie, ve které je šířka dráhy úzce spjata s libovolnými rodinami grafů uzavřenými pod nezletilými, má důležitou algoritmickou aplikaci [63] .

Aplikace

VLSI

Během vývoje VLSI byl problém dělení vrcholů původně studován jako způsob, jak rozdělit řetězce na menší subsystémy s malým počtem komponent na hranici mezi systémy [47] .

Otsuki, Mori, Kuh a Kashiwabara [64] použili tloušťku intervalu k modelování počtu vodičů potřebných v jednorozměrném uspořádání VLSI obvodů tvořených více moduly, které mají být propojeny síťovým systémem. V jejich modelu lze vytvořit graf, ve kterém vrcholy představují řetězce a ve kterém jsou dva vrcholy spojeny hranou, pokud jsou jejich řetězce připojeny ke stejnému modulu. To znamená, že pokud jsou moduly a řetězce chápány jako vrcholy a hyperhrany hypergrafu , pak graf z nich vytvořený je spojnicovým grafem hypergrafu . Intervalová reprezentace supergrafu tohoto spojnicového grafu spolu s vybarvením supergrafu popisuje uspořádání sítí podél horizontálních drah (jedna dráha pro každou barvu), takže moduly mohou být uspořádány podél drah v lineárním pořadí a připojeny k požadované sítě. Z toho, že intervalové grafy jsou dokonalé [65] , vyplývá, že počet barev potřebný pro optimální rozložení tohoto typu je roven číslu kliky intervalového doplňku řetězového grafu.

Stohování matice přepínačů [66] je specifický druh stohování CMOS VLSI pro obvody logické algebry . Při maticovém stackování přepínačů se signál šíří po "čarách" (vertikálních segmentech), přičemž každý přepínač je tvořen posloupností prvků umístěných na vodorovném segmentu. Horizontální segmenty každého přepínače tedy musí protínat vertikální segmenty každého řádku, který slouží jako vstup nebo výstup přepínače. Stejně jako u skládání Otsuki, Mori, Kuha a Kashiwabara [64] lze tento typ skládání, který minimalizuje počet svislých čar, vypočítat výpočtem šířky dráhy grafu, který má čáry jako vrcholy a pár čar patřících do grafu. přepínač jako hrany [67] . Stejný algoritmický přístup lze také použít k modelování problémů se stohováním v programovatelných logických integrovaných obvodech [68] [69] .

Vizualizace grafu

Pathwidth má několik aplikací pro vizualizaci grafů :

Design kompilátoru

Při překladu vysokoúrovňových programovacích jazyků vzniká pathwidd v problému přeuspořádání lineárního kódu (tedy kódu bez řídicí logiky - přechodů a smyček) tak, aby všechny hodnoty vypočítané v kódu mohly být ve strojových registrech , a není vytlačen do hlavní paměti. V této aplikaci je přeložený kód reprezentován jako směrovaný acyklický graf (DAG), ve kterém vrcholy představují vstupní hodnoty pro kód a hodnoty vypočítané jako výsledek operací v rámci kódu. Hrana z uzlu x do uzlu y v tomto NAG představuje skutečnost, že hodnota x je jedním ze vstupů operace y . Topologické řazení vrcholů v tomto NAG představuje správné řazení kódu a počet registrů potřebných k provedení kódu v tomto pořadí je dán rozdělením vrcholů uspořádání [74] .

Pro jakýkoli pevný počet w registrů ve stroji lze v lineárním čase určit, zda lze kus lineárního kódu přeuspořádat tak, že kód vyžaduje nejvýše w registrů. Pokud je vrcholová separace topologického uspořádání nejvýše w , nemůže být minimální vertexová separace mezi všemi uspořádáními větší, takže neorientované grafy vytvořené ignorováním orientace NAG popsané výše musí mít šířku cesty nejvýše w . Je možné ověřit, zda je to pravda, pomocí známých algoritmů rozhoditelné šířky cesty s pevnými parametry, a pokud je to pravda, najít rozklad cesty pro neorientované grafy v lineárním čase za předpokladu, že w je konstanta. Jakmile je nalezen stromový rozklad, lze pomocí dynamického programování nalézt topologické uspořádání s šířkou w (pokud takové existuje), opět v lineárním čase [74] .

Lingvistika

Karnai a Tutsa [75] popsali aplikaci šířky cesty na zpracování přirozeného jazyka . V této aplikaci jsou věty modelovány jako grafy, kde vrcholy představují slova a hrany představují vztahy mezi slovy. Pokud například přídavné jméno upravuje podstatné jméno, pak má graf mezi těmito dvěma slovy okraj. Kvůli omezené kapacitě lidské krátkodobé paměti Miller [76] , Kornai a Tutsa tvrdí, že tento graf musí mít omezenou šířku dráhy (konkrétněji tvrdí, že tato šířka dráhy nepřesahuje šest), jinak by lidé nebyli schopni správně rozpoznat řeč.

Exponenciální algoritmy

Mnoho problémů teorie grafů může být efektivně řešeno na grafech s malou šířkou dráhy pomocí dynamického programování , založeného na rozkladu dráhy grafu [11] . Pokud je například dáno lineární uspořádání vrcholů grafu G s n vrcholy a hodnota separace vrcholů je rovna w , pak je možné najít největší nezávislou množinu grafu G v O(2 w n ) čas [43] . Na grafu s omezenou šířkou dráhy tento přístup vede k algoritmům s pevně, parametricky rozhodnoutelnou šířkou dráhy [67] . Takové výsledky se v literatuře často nenacházejí, protože patří do skupiny podobných algoritmů parametrizovaných šířkou stromu. Šířka cesty se však objevuje i v algoritmech dynamického programování založených na šířce stromu při měření kapacitní složitosti těchto algoritmů [12] .

Stejnou techniku ​​dynamického programování lze aplikovat na grafy s neomezenou šířkou cesty, což vede k algoritmům, které řeší neparametrizované problémy na grafech v exponenciálním čase . Například kombinace přístupu dynamického programování se skutečností, že kubické grafy mají šířku cesty n /6 + o( n ) ukazuje, že pro kubické grafy lze maximální nezávislou množinu sestavit v O(2 n /6 + o( n ) ) čas.který je rychlejší než dříve známé metody [43] . Podobný přístup vede k vylepšeným exponenciálním časovým algoritmům pro problémy maximálního řezu a minimální dominující množiny pro kubické grafy [43] a pro některé další NP-tvrdé optimalizační problémy [77] [78] .

Viz také

Poznámky

  1. ↑ Diestel, Kühn, 2005 .
  2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
  3. ↑ 1 2 Bodlaender, 1998 .
  4. ↑ Mnoho pojmů použitých v článku lze nalézt v úvodu disertační práce F. V. Fomina (( Fomin 1996 ))
  5. ↑ 12 Robertson , Seymour, 2003 .
  6. ↑ 1 2 Kashiwabara, Fujisawa, 1979 ; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 ; Lengauer 1981 ; Arnborg, Corneil, Proskurowski, 1987 .
  7. ↑ 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992 .
  8. ↑ 1 2 3 Bodlaender (1996 ); Bodlaender, Kloks (1996 )
  9. ↑ 1 2 Bodlaender, 1994 .
  10. ↑ 12 Möhring , 1990 ; Scheffler, 1990 ; Ellis, Sudborough, Turner, 1994 ; Coudert, Huc, Mazauric, 1998 ; Peng, Ho, Hsu, Ko, Tang, 1998 ; Škodanis, 2000 ; Škodanis (2003 ).
  11. ↑ 12. Arnborg , 1985 .
  12. ↑ 1 2 Aspvall, Proskurowski, Telle, 2000 .
  13. ↑ Bodlaender, 1994 , str. 1–2.
  14. ↑ Bodlaender, 1998 , s. 13, věta 29.
  15. ↑ Ellis, Sudborough, Turner, 1983 .
  16. ↑ 1 2 3 Kinnersley, 1992 .
  17. ↑ Bodlaender, 1998 , s. Věta 51.
  18. ↑ Kirousis, Papadimitriou, 1985 .
  19. ↑ Proskurowski, Telle, 1999 .
  20. ↑ Korach, Solel, 1993 , s. 99, Lemma 3.
  21. ↑ Bodlaender, 1998 , s. 24, věta 47.
  22. ↑ Korach, Solel, 1993 , s. 99, Lemma 1.
  23. ↑ Bodlaender, 1998 , s. 24, věta 49.
  24. ↑ Korach, Solel, 1993 , s. 99, věta 5.
  25. ↑ Bodlaender, 1998 , s. 30, věta 66.
  26. ↑ Scheffler (1992 ) dává silnější vazbu na  šířku cesty log 3 (2 n + 1) n -vertexového lesa.
  27. ↑ Korach, Solel, 1993 , s. 100, věta 6.
  28. ↑ Bodlaender, 1998 , s. 10, důsledek 24.
  29. ↑ Gurski, Wanke, 2007 .
  30. ↑ Golovach, 1993 .
  31. ↑ Bodlaender, 1998 , s. 10, důsledek 23.
  32. ↑ Bodlaender, 1998 , s. 9, věta 20.
  33. ↑ Alon, Seymour, Thomas, 1990 .
  34. ↑ Bodlaender, Fomin, 2002 .
  35. ↑ Coudert, Huc, Sereni, 2007 .
  36. ↑ Fomin, Thilikos, 2007 .
  37. ↑ Amini, Huc, Perennes, 2009 .
  38. ↑ Fomin, 2003 .
  39. ↑ 1 2 Bodlaender, Möhring, 1990 .
  40. ↑ 1 2 Bodlaender, Kloks, Kratsch, 1993 .
  41. ↑ 1 2 Habib, Möhring, 1994 .
  42. ↑ 12 Garbe , 1995 .
  43. ↑ 1 2 3 4 Fomin, Høie, 2006 .
  44. ↑ Fomin, Kratsch, Todinca, Villanger, 2008 .
  45. ↑ Downey, Fellows, 1999 , s. 12.
  46. ↑ de Fluiter, 1997 .
  47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
  48. ↑ 12 Gusted , 1993 .
  49. ↑ Kloks, Kratsch, Müller, 1995 . Akordické domino je akordický graf, ve kterém jakýkoli vrchol patří nejvýše dvěma maximálním klikám
  50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
  51. ↑ 1 2 Kloks, Bodlaender, 1992 .
  52. ↑ Garbe (1995 ) připisuje tento výsledek disertační práci Tona Cloxe z roku 1993. Garbeho polynomiální časový algoritmus pro grafy srovnatelnosti intervalového uspořádání tento výsledek zobecňuje, protože každý akordický graf musí být grafem srovnatelnosti tohoto typu.
  53. ↑ Suchan, Todinca, 2007 .
  54. ↑ Feige, Hajiaghayi, Lee, 2005 .
  55. ↑ Guha, 2000 .
  56. ↑ 12 Robertson , Seymour, 2004 .
  57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991 .
  58. ↑ Diestel, 1995 .
  59. ↑ Cattell, Dinneen, Fellows, 1996 .
  60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
  61. ↑ 1 2 Bodlaender, 1998 , str. osm.
  62. ↑ Kinnersley, Langston, 1994 .
  63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
  64. ↑ 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 .
  65. ↑ Berge, 1967 .
  66. ↑ Lopez, Právo, 1980 .
  67. ↑ 12 Fellows , Langston, 1989 .
  68. ↑ Möhring, 1990 .
  69. ↑ Ferreira, Song, 1992 .
  70. ↑ Hlinený, 2003 .
  71. ↑ Suderman, 2004 .
  72. ↑ Dujmović, Fellows, Kitching et al., 2008 .
  73. ↑ Dujmovic, Morin, Wood, 2003 .
  74. ↑ 1 2 Bodlaender, Gustedt, Telle, 1998 .
  75. ↑ Kornai, Tuza, 1992 .
  76. ↑ Miller, 1956 .
  77. ↑ Kneis, Mölle, Richter, Rossmanith, 2005 .
  78. ↑ Björklund, Husfeldt, 2008 .

Literatura