Dekompozice grafů, algoritmy a minory Další autorův výběr tématu nás zavede blíže ke strukturální teorii grafů, k různým jejich dekompozicím, grafovým minorům a navazujícím efektivním algoritmům pro jinak těžké problémy. Obecnou inspirací nám je poměrně zřejmý fakt, že většinu jinak těžkých problémů lze řešit snadno a efektivně na stromech. Proto se podíváme na grafy, které jsou svým způsobem „stromům blízké", ve smyslu existence jejich vhodné dekompozice. Vrcholem této lekce je formulace hlavního výsledku takzvané „Graph Minors Theory" od Robertsona a Seymoura, který lze bez nadsázky prohlásit za asi největší výsledek, kterého dosud teorie grafů dosáhla (i v porovnání s Větou o čtyřech barvách), c Stručný přehled lekce • Úvodní zamyšlení nad řešením obtížných problémů. • Stromová šířka grafu z mnoha stran. Některé jiné „šířkové" parám. • Ukázky použití dekompozic grafů na efektivní algoritmy. • Něco o grafových minorech a strukturální teorii. leny. Fl f\; :l: MA010: Dekompozice a minory 10.1 Obtížné problémy na speciálních grafech V Lekci 7 jsme uvedli některé „neřešitelně obtížné", přesněji TVP-těžké grafové problémy, například 3-obarvení grafu nebo nezávislá množina vrcholů, d Oba tyto problémy snadno vyřešíme na intervalových grafech. Algoritmus 10.1. Nalezení nezávislé množiny v intervalovém grafu Předpokládejme, že graf G je daný svou intervalovou reprezentací (v případě potřeby je možno tuto reprezentaci efektivně sestrojit). Maximální nezávislou množinu nalezneme následovně. • Uspořádáme intervaly reprezentující G podle jejich pravých konců, c • Do nezávislé množiny hladově (v tomto uspořádání) vložíme vždy první interval neprotínající se s předchozími vybranými. >etr Hliněný, Fl MU Brno 2 Fl: MA010: Dekompozice a minor r Také na obecnějších chordálnich grafech můžeme navrhovat rychlé a povětšinou i snadné algoritmy. Algoritmus 10.2. Určení barevnosti chordálního grafu • Snadno zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.4). c • Graf G je fc-degenerovaný, kde k = u>(G) — 1 je největší stupeň simpliciálního vrcholu v některém kroku simpliciální dekompozice G. Hladově tudíž můžeme G obarvit k+í barvami a to je optimální (neboť máme v G kliku velikosti k + 1). Algoritmus 10.3. Nalezení nezávislé množiny chordálního grafu • Opět zkonstruhujeme simpliciální dekompozici našeho grafu G (Věta 9.4). • V pořadí této dekompozice hladově přidáváme vrcholy do nezávislé množiny. (Tento postup je přímým zobecněním Algoritmu 10.1, viz také Věta 9.5.) Možná zobecnění? Zajímavou a užitečnou otázkou teď je, jak takové postupy zobecnit na širší třídy grafů, které mají nějakou specifickou omezující (ale ne příliš) vlastnost - „parametr". s_ linený, Fl MU Brn Fl: MA010: Dekompozice a minory 10.2 Tree-width - čtyři definice Název „tree-width" byl zaveden Robersonem a Seymourem počátkem 80-tých let, ale pak se ukázalo, že ekvivalentní definice již uvažovali matematici léta před nimi, například v souvislosti s takzvanými „fc-trees" nebo se simpliciálními dekompozicemi. (Důsledkem tohoto vývoje je také bohatost různých definic stejného pojmu. ..) c Připomeňme, že velikost největší kliky v grafu G se označuje u>(G). Definice: Stromovou šířkou (tree-width) grafu G nazveme nejmenší přirozené k takové, že existuje chordální graf H s u>(H) = k + 1 obsahující G jako podgraf (H D G). Například každý podgraf následujícího chrodálního grafu má tree-width < 2: Kde je však v této definici nějaký „strom"? Je, ale skrytý - podívejte se na Větu 9.5 popisující chordální grafy jako průnikové grafy podstromů ve stromě. — — Jinou možnost popisu ukazuje: Definice: Vrcholy V(G) grafu G uspořádáme do posloupnosti (permutace) (vi, V2, ■ ■ ■, vn). Pro i = 1,2,..., n definujme í{ví) jako počet všech indexů j G {1,..., i — 1} takových, že vrcholy ví a Vj jsou v G spojeny cestou používající pouze vrcholy z množiny {vj,ví, Vj+i, ...,«„}. Druhou stromovou šířkou grafu G nazveme nejmenší hodnotu výrazu max„ l(ti) přes všechny permutace vrcholů V(G). Všimněte si, že uspořádání vrcholů z této definice je vlastně zpětnou simpliciální dekompozicí chordálního grafu H D G z předchozí definice (viz také Věta 9.4). V nakresleném příkladě grafu Cb vidíme uspořádání vrcholů se šířkou 2. (Tečkované hrany ukazují tzv. chordální doplnění grafu, relevantní k první definici tree-width.) etr Hliněný, Fl MU Brno 5 Fl: MA010: Dekompozice a minory Ještě další, značně odlišný, přístup má tato definice: Definice: Pro libovolný strom T uvažujeme (libovolné) zobrazení t : E (G) —> V (T). Pro vrchol t G V (T) označíme Ti,... ,Td jednotlivé komponenty lesa T — t a Fi = T-l(V{Ti)). Označme £T(t) = \V(G)\ + (d - 1) • c(G) -J2etr Hliněný, Fl MU Brno Fl: MA010: Dekompozice a minor Definice: Cestní dekompozici a šířku (path-width) grafu G definujeme stejně jako v Definici 10.4, jen požadujeme navíc, aby T byla cesta, d Definice: Vrcholy V(G) grafu G uspořádáme do posloupnosti (permutace) (ví, V2, ■ ■ ■, vn). Bandwidth grafu G definujeme jako nejmenší hodnotu výrazu max„.„.e£(G) \i — j\ přes všechny permutace vrcholů V(G). c Větvené dekompozice Graf je kubický, pokud má všechny vrcholy stupně 3. Strom je podkubický, pokud má všechny vrcholy stupně < 3. Definice: Pro libovolný graf G a podmnožinu X C E (G) definujeme funkci souvislosti Xg(X) jako počet vrcholů G, které jsou konci některých hran z X i hran z E(G) \X [separace množiny X). etr Hliněný, Fl MU Brno 9 Fl: MA010: Dekompozice a minory G9 Definice 10.7. Větvená dekompozice grafu G Nechť T je podkubický strom a t : E (G) —> L(T) je bijekce hran grafu G do listů L(T) stromu T. Pro každou hranu x stromu T definujeme šířku x jako \q{X), kde X = t-1(V(T1)) pro jednu z komponent Ti, T2 lesa T - x. e[x šířka (x) := AG(X) = AG(T \ X) c Pak šířkou dekompozice T,t je maximální šířka ze všech hran T a větvenou šířkou grafu G je nejmenší možná šířka větvené dekompozice G. c etr Hliněný, Fl MU Bn FhMAOlO^^DekompoziceaminoiY af ae ef de cd V^ df bf - cf be ■ ac ad 5— ab Ks bd \ bc ce Věta 10.8. Pokud graf G má stromovou šířku t a větvenou šířku 6 > 1, tak 3 b<í+1< -b 2 etr Hliněný, Fl MU Bn FkMAOlO^^DekompoziceaminotY Jiný přístup Nechť G je gráfa X C V (G). Jako funkci hodnosti řezu 7g(T) na množině F označíme hodnost X x (V \ X)-matice A = (a^-) nad binárním tělesem GF(2), kde aUiV = 1 pro u G X a v GV\X, právě když uv je hranou v G. c Definice 10.9. Ranková dekompozice grafu G Nechť T je podkubický strom a t : V(G) —> L(T) je bijekce vrcholů grafu G do listů i(T) stromu T. Pro každou hranu x stromu T definujeme šířku x jako 70(X), kde X = T-1(Vr(Ti)) pro jednu z komponent Ti, T2 lesa T - x. n Pak šířkou dekompozice T,t je maximální šířka ze všech hran T a rankovou šířkou grafu G je nejmenší možná šířka rankové dekompozice G. etr Hliněný, Fl MU Bn FhMAOlO^^DekompoziceaminoiY 10.4 Efektivní algoritmy na dekompozicích Již víme z 7.17, že určení velikosti největší nezávislé množiny v grafu je TVP-úplný problém. Stromová dekompozice fixní šířky však tento problém umožňuje řešit velice snadno. Algoritmus 10.10. Nezávislá množina na stromové dekompozici Danou stromovou dekompozici vstupního grafu si libovolně „zakořeníme". • V každém listě dekompozice vyřešíme problém hrubou silou v konstantním čase.n • Ve směru od listů ke kořeni sbíráme následující informaci: V každém balíku B dekompozice, pro každou X C B, velikost největší nezávislé množiny / v grafu indukovaném na podstromu pod B takové, že I P\ B = X. d • Vzhledem k interpolační vlastnosti naší dekompozice lze výše popsanou informaci v každém balíku dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace ze všech jeho potomků v dekompozici. Výsledný algoritmus pracuje v čase úměrném počtu uzlů dekompozice, tedy v lineárním čase! c etr Hliněný, Fl MU________________________________________________MA010: Dekompozice a minory Další problém hledání párování v grafu sice je polynomiálně řešitelný, ale zjišťování počtu všech párování už je #V-úplné, neboli stejně těžké (beznadějné) jako výpočet permanentu matice nebo spočítání všech řešení SAT problému. Algoritmus 10.11. Počet párování na větvené dekompozici Opět si větvenou dekompozici vstupního grafu libovolně „zakořeníme". • V každém listě dekompozice je řešení triviální, c • Ve směru od listů ke kořeni sbíráme následující informaci: V každé hraně dekompozice, pro každou podmnožinu X C S vrcholů separace S indukované touto hranou v dekompozici, počet všech párování, která ze separace S „obsazují" právě vrcholy X. c • Opět lze výše popsanou informaci na každé hraně dekompozice zjistit v konstantním čase pouze ze znalosti stejné informace z obou jejich podstromů v dekompozici (vzájemným vynásobením a sečtením počtů). Výsledný algoritmus pracuje v čase úměrném počtu hran dekompozice, tedy opět v lineárním čase. c etr Hliněný, Fl MU________________________________________________MA010: Dekompozice a minory Jeden všeobecný výsledek Nápadná vzájemná podobnost předchozích algoritmů určitě není náhodná, chtěli jsme jimi ilustrovat jeden důležitý obecný princip, který objevili postupně [Courcelle / Arnborg, Lagergren, Seese / Borie, Parker, Tovey]. Věta 10.12. Každá vlastnost grafů, která je vyjádřitelná v tzv. (E)MSO jazyce, se dá vypočítat v lineárním čase pro všechny grafy omezené stromové šířky. Pro zjednodušení nebudeme přesně definovat, co (E)MSO jazyk znamená, ale zhruba jde o jazyk, který má dovoleno kvantifikovat přes podmnožiny vrcholů a hran grafu a enumerovat počty prvků množin. Většina grafových vlastností, které jsme zatím probírali, spadá do této kategorie. etr Hliněný, Fl MU________________________________________________MA010: Dekompozice a minory 10.5 Minory v grafech Definice: Říkáme, že graf G je minorem grafu H, pokud lze G získat z H kontrakcemi hran a vypouštěním vrcholů a hran. Robertson-Seymourova věta Věta 10.13. Mějme libovolnou grafovou vlastnost , která je uzavřená na minory (tj. pokud G má , pak každý minor G má také ). Pak existuje konečně mnoho grafů ŕ\,..., Fe (zakázané minory) takových, že G má právě když G neobsahuje minor isomorfní žádnému z ŕ\,..., Fg. Mimo jiné lze tudíž vlastnost rozhodnout v čase 0(n3) pro každý n-vrcholový graf G. Poznámka: Tato věta je zcela nekonstruktivní, neboli nepodává žádný návod, jak zmíněný algoritmus sestrojit! sny, Fl MU Brn :l: MA010: Dekompozice a minory >/