Efektivní předzpracování a parametrizované algoritmy (MI-PAM)

Od letního semestru 2018/19 jsou stránky předmětu přesunuty na novou adresu https://courses.fit.cvut.cz/MI-PAM/.

Základní informace

Přednášejícím je Ondřej Suchý.

Místo konání

Hodnocení

Během semestru budou zadávány domácí úkoly, celkem nejméně za 70 bodů. Na zápočet je potřeba získat 20 bodů. Termín pro odevzdání úkolů je typicky do cvičení, které následuje za aspoň 13 dní. Na cvičení buď předvede řešení úkolu někdo ze studentů, nebo přednášející, nebo úkol doplníme nápovědou, která může změnit jeho bodovou hodnotu, nebo jej odložíme na další cvičení. Za zdařilé předvedení příkladu student získá další 1 bod. Předpokládám, že úkoly budete odevzdávat vypracované na papíře, případně předvedete, jinou formu prosím konzultujte předem.

Předmět bude zakončen zkouškou. Každý student dostane 2 otázky, jednu tématickou a jednu definici (viz seznam otázek). K tématu by měl být student schopen něco říct, u definice znát její obrysy, nikoliv nutně přesné znění. Po písemné přípravě pak proběhne ústní zkouška, která rozhodne o známce.

V KOSu je vypsán nějaký termín zkoušky. Pokud byste chtěli přijít na zkoušku jindy, nebo bez přihlášení, napište mi email, abych tu byl. Zkoušky začínají vždy u mě v pracovně TH: A-1229, ale nelze vyloučit pozdější přesun jinam, pokud bychom například v pracovně rušili ostatní.

Průběžné výsledky:

Probraná témata

• 21.2. Přednáška: O(2^km) algoritmus pro Vrcholové pokrytí. Základní pojmy: Parametrizovaný problém, parametrizovaně dostupný, fpt-algoritmus, třídy FPT a XP a jejich vztah; zmíňka o třídách W[1] a W[2] a jejich vztazích k předchozím. Možné parametrizace: standardní (velikost řešení), duální, strukturální, nad mezí (ukázka pro Max-2-Sat nad mezí 3m/4), kombinace. Vylepšený (1,466^k) prohledávací strom pro Vrcholové pokrytí. (zhruba stránky 3-7, 11-14 a 53 z knihy Parameterized Algorithms (dále jen PA), viz doporučená literatura)
  Cvičení se nekonalo - byly jen zadány domácí úkoly.
  Domácí úkoly:
  1. Označme PlusFPT třídu všech parametrizovaných problémů, pro které existuje algoritmus pracující v čase f'(k)+(k+|x|)^c'. Ukažte, že pro každý parametrizovaný problém L platí, že L je v FPT právě tehdy, když je v PlusFPT. (2 body)
  2. Ukažte, že klika je parametrizovaně dostupná vzhledem k maximálnímu stupni vstupního grafu Δ(G). (3 body)
  3. Ukažte, že Nezávislá množina je FPT vzhledem k velikosti řešení k v rovinných grafech. (3 body)
  4. Uvažte následující problém:
     Cluster Editing
     Vstup: Graf G, k nezáporné celé.
     Otázka: Lze G transformovat pomocí nejvýše k přidávání a mazání hran na graf, který je vrcholově disjunktním sjednocením klik?
     Ukažte, že existuje algoritmus, který řeší Cluster Editing v čase O(3^kn^O(1)). (3 body)
  5. Pro nějakou pevně zvolenou konstantu d uvažte následující problém:
     d-Hitting Set
     Vstup: Množina prvků U, systém jejích podmnožin F ⊆ 2^U takový, že každá množina je velikosti nejvýše d, k nezáporné celé.
     Otázka: Existuje S podmnožina U velikosti nejvýše k taková, že každá množina A z F obsahuje aspoň jeden prvek z S (tedy S ∩ A ≠ ∅)?
     Ukažte, že tento problém je FPT vzhledem k velikosti řešení k. (3 body)
• 28.2. Přednáška: Vylepšený (1,466^k) prohledávací strom pro Vrcholové pokrytí - jak se to spočítá. Předzpracování - dvě jednoduchá pravidla pro VP a Bussův O(k²) kernel. Korektní pravidlo, redukovaná, ekvivalentní instance. Kernelizace. Rozhodnutelný problém má kernel právě když je FPT. (str. 51-56, 17-22 PA, k dispozici je textík k přednášce)
  Domácí úkoly:
  6. Vymyslete algoritmus pro 3-SAT pracující v čase O((2-ε)ⁿ) pro nějaké ε > 0, kde n je počet proměnných ve vstupní formuli. (4 body)
  7. Uvažte následující problém:
     Point Line Cover
     Vstup: n bodů v rovině, k nezáporné celé.
     Otázka: Existuje k přímek v rovině tak, že každý ze zadaných bodů leží na alespoň jedné z těchto přímek?
     Ukažte, že tento problém má kernel s O(k²) body (nejedná se o kernel v pravém slova smyslu, neboť neomezujeme délky zápisu jednotlivých bodů). (3 body)
  8. Uvažte následující problém:
     d-Bounded Degree Deletion
     Vstup: Graf G, k nezáporné celé, d nezáporné celé.
     Otázka: Lze z G smazat nejvýše k vrcholů tak, aby ve výsledném grafu byl maximální stupeň nejvýše d?
     Ukažte, že tento problém má kernel velikosti (k+d)^O(1). (4 body)
  9. Uvažte následující problém:
     Dělení Množin
     Vstup: Množina prvků U, systém jejích podmnožin F ⊆ 2^U, k nezáporné celé.
     Otázka: Existuje obarvení množiny U pomocí dvou barev takové, že alespoň k množin z F obsahuje prvky obou barev?
     Ukažte, že tento problém má kernel s 2k množinami a universem U s O(k²) prvky (nebo alespoň jednu z podmínek za méně bodů). (5 bodů)
• 8.3. Přednáška: Další dvě pravidla pro Vrcholové pokrytí - stupeň 1 a 2. Prokládání omezeného prohledávacího stromu s kernelizací - O(1.3803^k + n²) algoritmus pro Vrcholové pokrytí. O(k³) kernel pro 3-Hitting Set. Kernel o 2k vrcholech pro Vrcholové pokrytí založený na lineárním programovaní (Nemhauser-Trotter) s důkazem. (první dvě v PA moc nejsou, pro Hitting Set jiný přístup na str. 38-39, třetí téma str. 33-36 PA)
  Cvičení: Vyřešeny příklady 1 až 5. Pro příklad 3 zbývá druhá možnost řešení, viz příklad 14.
  Domácí úkoly:
  10. Ukažte, že následující pravidlo pro Vrcholové pokrytí je korektní:
      Pravidlo 4: Je-li v stupně 2 v G, N(v)={u,w} a
      1. {u,w} ∈ E(G), potom smaž u,v,w a polož k:=k-2;
      2. {u,w} ∉ E(G), potom smaž u,v,w, přidej u' takové, že N(u')=(N(u)∪N(w))∖ {v} a polož k:=k-1.
      (4 body za celé, 2 za část a nebo b)
  11. Pro d > 3 ukažte, že d-Hitting Set má kernel o velikosti O(k^d). (4 body za d=4, 6 bodů za d=20)
  12. Uvažte následující problém:
      Maximum Satisfiability (MaxSat)
      Vstup: Formule φ v CNF, k nezáporné celé.
      Otázka: Lze splnit alespoň k klauzulí z φ?
      
      1. Ukažte, že pro každou klauzuli C, která obsahuje alespoň k různých literálů, a každou formuli ψ s nejvýše (k-1) klauzulemi platí, že pokud lze splnit ψ, lze splnit také ψ∧C. (4 body)
      2. Ukažte kernel o O(k²) literálech pro MaxSat. (4 body)
      3. Ukažte omezený prohledávací strom pro MaxSat pracující v čase O(k^O(k)n^O(1)). (3 body)
      Poznámka: Tvrzení z části a) lze využít k řešení b) a c) i pokud a) nebudete řešit.
  13. Řekneme, že graf je chordální, pokud neobsahuje kružnici na aspoň čtyřech vrcholech jako indukovaný podgraf.
      Uvažte následující problém:
      Minimum Fill-In
      Vstup: Graf G, k nezáporné celé.
      Otázka: Lze G udělat chordálním přidáním nejvýše k hran?
      
      1. Ukažte, že tento problém je FPT vzhledem ke k. (5 bodů)
      2. Ukažte, že pro tento problém existuje algoritmus pracující v čase O(2^O(k)n^O(1)). (7 bodů)
      Body buď za a) nebo za b).
  14. Ukažte, že Nezávislá množina v rovinných grafech má lineární kernel. (2 body)
• 14.3. Přednáška: Polynomiální algoritmus pro řešení lineárního programování pro Vrcholové pokrytí. O(4^k-LP(G)n^O(1)) algoritmus pro Vrcholové pokrytí, analýza jeho časové složitosti. Neexistence polynomiálních kernelů pro některé problémy - zatím jen myšlenka. (str. 36-38, 60-64, 524-525 PA)
  Domácí úkoly:
  15. Ukažte, že vrcholové pokrytí je FPT vzhledem k parametru λ(G,k)=k-m(G), kde m(G) je velikost největšího párování v G. (2 body)
  16. Nechť G lze získat ze stromu přidáním ℓ hran.
      
      1. Najděte O(2^ℓn^O(1)) algoritmus pro (vrcholově) Vážené vrcholové pokrytí na takových grafech. (2 body)
      2. Najděte O(ℓ) kernel pro (nevážené) vrcholové pokrytí na takových grafech. (3 body)
• 21.3. se přednáška (ani cvičení) nekonaly, přednášející (a cvičící) byli v zahraničí.
• 29.3. Přednáška: Neexistence polynomiálních kernelů pro některé problémy - definice OR-skládání, věta: pokud se NP-těžký problém OR-skládá do parametrizovaného problému, pak tento nemá polynomiální kernel, nebo NP ⊆ coNP/poly a polynomiální hierarchie se zřítí na třetí patro (bez důkazu). Použití: k-Cesta (obsahuje G cestu délky k?) nemá polynomiální kernel (pokud ...), Hitting Set nemá polynomiální kernel vzhledem k velikosti univerza (pokud ...). Zmíňka o těsných dolních mezích pro velikost kernelu pro d-Hitting Set, komunikačních protokolech a Turingových kernelech. (str. 529-531, 533-534, složitější OR-skládání pro jiný problém 534-537, 551-552 PA)
  Domácí úkoly:
  17. Ukažte, že pokud NP ⊈ coNP/poly, pak Klika nemá polynomiální kernel vzhledem k maximálnímu stupni vstupního grafu Δ(G). (2 body)
  18. Ukažte, že Klika má polynomiální Turingův kernel vzhledem k maximálnímu stupni vstupního grafu Δ(G). (2 body)
  19. Uvažte následující problém:
      Disjoint Factors
      Vstup: Slovo t ∈ Σ^*, kde Σ={s₁, ..., s_r}.
      Otázka: Existují souvislá disjunktní podslova w₁, ..., w_r slova t taková, že pro každé i slovo w_i má délku aspoň 2 a začíná a končí symbolem s_i?
      Ukažte, že pokud NP ⊈ coNP/poly, pak Disjoint Factors nemá polynomiální kernel vzhledem k r=|Σ|.
      Můžete předpokládat, že Disjoint Factors je NP-úplný. (4 body)
• 4.4. Přednáška: Dynamické programování - O(2ⁿn²) algoritmus pro Problém obchodní cestující (Held & Karp). Princip inkluze a exkluze - O(2ⁿn³) algoritmus pro Hamiltonovskou kružnici využívající pouze polynomiální prostor. Barevné kódování (Color coding) - dynamické programování pro Barevnou k-cestu (v grafu s vrcholy obarvenými k barvami nalézt cestu, která používá každou barvu právě jednou) v O(2^kn²), pravděpodobnost chyby při náhodném obarvení, derandomizace pomocí (n,k)-perfektního systému hashovacích funkcí, k-Cestu lze řešit v čase O(e^k2^kk^{O(log k)}n²log n). (str. 322-324, 104-105, 100, 118 PA)
  Cvičení: Vyřešeny příklady 6-10, 12a), 12b) a 14.
  Domácí úkoly:
  Trvají dosud nevyřešené příklady, tj. 11, 12c) a 15-19.
  20. Mějme města c₁,...,c_n zadána jako různé body v rovině. Vzdálenost mezi nimi je dána eukleidovskou vzdáleností. Ukažte, že pak Problém obchodní cestující lze řešit v čase O(2^kn^O(1)), kde k je počet měst, která neleží na hranici konvexního obalu množiny {c₁,...,c_n}. (4 body)
  21. Ukažte, že následující problém je FPT vzhledem ke k:
      Disjunktní trojúhelníky
      Vstup: Graf G, k nezáporné celé.
      Otázka: Existuje v G k vrcholově disjunktních trojúhelníků?
      (3 body)
  22. Uvažme následující problém:
      Podstrom
      Vstup: Graf G, strom H.
      Otázka: Existuje v G podgraf izomorfní H?
      Ukažte, že tento problém je FPT vzhledem k |V(H)|. (4 body)
  23. Polynomiální algoritmus pro Vážené vrcholové pokrytí (vrcholy mají danou váhu a snažíme se najít pokrytí s co nejmenší váhou) na
      1. stromech (2 body)
      2. 5 x n mřížce (3 body)
  24. Polynomiální algoritmus pro Váženou dominující množinu (vrcholy mají danou váhu a snažíme se najít dominující množinu s co nejmenší váhou, množina je dominující, pokud každý vrchol grafu je buď v této množině, nebo v ní má nějakého souseda) na
      1. cestách (2 body)
      2. binárních zakořeněných stromech (3 body)
      3. libovolných stromech (5 bodů)
      4. 5 x n mřížce (5 bodů)
      Celkem lze za části a)-c) získat jen 5 bodů.
• 11.4. Přednáška: Iterativní komprese - Feedback Vertex Set (FVS) (smaž z grafu nejvýše k vrcholů, aby zbytek byl les) převod postupně na Kompresi FVS (navíc dostanu řešení velikosti k+1), na Disjunktní kompresi (navíc chci aby nové řešení bylo disjunktní se starým) a nakonec na FVS s lesní bipartizací (jako FVS, ale dostanu navíc rozdělení vrcholů na V₁ a V₂, obě indukují les, vrcholy mažu jen z V₁) s parametrem k+počet komponent G[V₂]. Řešení toho posledního pomocí prohledávacího stromu s málo listy, a pomocí tohohle postupně všech předchozích. Pro FVS vyjde O(5^kn³).
  Bipartizace grafu (smaž nejvýše k vrcholů, aby zbytek byl bipartitní): komprese v O(3^kkm), celý problém v O(3^kkmn). (str. 80-81, 86-88, 91-94 PA)
  Domácí úkoly:
  25. Ukažte, že Disjunktní komprese pro vrcholové pokrytí je řešitelná v polynomiálním čase. (2 body)
  26. Ukažte, že d-Hitting set lze řešit v čase O(((d-2)+1.39)^kn^O(d)). (Můžete použít algoritmy z přednášky.) (3 body za d=3, 4 body za obecné d)
  27. Uvažte následující problém:
      Cluster Vertex Deletion
      Vstup: Graf G, k nezáporné celé.
      Otázka: Lze G transformovat pomocí nejvýše k mazání vrcholů na graf, který je vrcholově disjunktním sjednocením klik?
      Ukažte, že existuje algoritmus, který řeší Cluster Vertex Deletion v čase O(2^kn^O(1)). (6 bodů)
• 18.4. Cvičení: Řešení úlohy 24 pomocí dynamického programování.
  Přednáška: Stromový rozklad a stromová šířka - definice, základní vlastnosti (stromová šířka stromu, lesa, kružnice, mřížky, podgrafu, pytel jako separátor); Hezký stromový rozklad a jak ho získat. Dynamické programování na hezkém stromovém rozkladu pro Váženou nezávislou množinu v O(2^tt³ n), kde t je šířka vstupního rozkladu. (str. 151-167 PA)
  Cvičení: Vyřešen příklad 11, dořešen příklad 12, vyřešeny příklady 13a), 15, 16a), 17, 18 a 23.
  Domácí úkoly: Trvají dosud nevyřešené příklady, tj. 13b), 16b), 19-22, 25 a dál.
  
  28. Ukažte, že pro kliku C v grafu G a libovolný stromový rozklad (T,β) grafu G existuje uzel x stromu T takový, že C ⊆ V_x. (4 body)
  29. Ukažte, že velikost nejmenší dominující množiny v grafu G lze určit v čase O(c^t n), pro nějakou konstantu c, pokud je na vstupu stromový rozklad šířky t. (4 body)
• 25.4. se přednáška nekonala, značná část studentů byla ze studijních důvodů mimo Prahu.
• 2.5. Přednáška: Aplikace stromové šířky - Courcellova věta (MSOL (Monadic Second Order Logic) formule lze rozhodovat v lineárním čase na grafech omezené stromové šířky; bez důkazu, jen idea), příklady pro 3-barevnost a Dominující množinu; zmíňka o použití na obecné relační struktury, skrytých konstantách a implementaci Sequoia.
  Zmíňka o obecné verzi Color Coding algoritmu.
  Zjišťování stromové šířky - je to NP-úplné, FPT, ale nejčastěji se to 4-aproximuje v čase O(8^tt²n²); na rovinných grafech to lze 1,5-aproximovat v čase O(n³); má-li rovinný graf kostru výšky ℓ (speciálně je-li ℓ-vnějškově rovinný), pak má stromovou šířku ≤ 3ℓ.
  Aproximační schémata podle Bakerové - pro libovolné ε > 0 lze na rovinných grafech v čase O(2^O(1/ε)n) a) (1-ε)-aproximovat Váženou nezávislou množinu b) (1+ε)-aproximovat Váženou dominující množinu. Důkaz. (str. 177-184, 190-191, 211-214 (trošku jiné použití posouvací techniky) PA)
  Cvičení: Vyřešeny příklady 16b), 19-22 a 25.
  Domácí úkoly: Trvají dosud nevyřešené příklady, tj. 13b), 26 a dále.
  
  30. Popište "S je feedback vertex set vstupního grafu" v MSOL. (4 body)
  31. Popište "má Hamiltonovskou kružnici" v MSOL. (3 body)
  32. Nechť G je vnějškově rovinný. Najděte stromový rozklad šířky 2. (3 body)
• 9.5. Přednáška: Definice - kontrakce hrany, minor, třída uzavřená na minory; Věty: Pro třídu uzavřenou na minory existuje konečná obstrukční sada zakázaných minorů. Otestovat zda H je minorem G lze v čase O(f(H) |V(G)|³); Důsledky: pro každou třídu uzavřenou na minory existuje O(n³) algoritmus (ale většinou se nezná); Třída grafů s Vrcholovým pokrytím velikosti ≤k uzavřená na minory - Neuniformní FPT (pro každé pevné k existuje (jiný) algoritmus běžící v čase O(n^c)). Obecně platí pro každý problém, který lze formulovat jako: "lze smazat k vrcholů, aby výsledek byl v dané třídě uzavřené na minory?"; Grafy stromové šířky ≤ t jsou uzavřené na minory.
  Má-li rovinný graf stromovou šířku ≥ t, pak obsahuje mřížku t/6 x t/6 jako minor.
  Příklad aplikace na bidimensionální problémy - O(2^{O(√ k)}n + n³) algoritmus pro Vrcholové pokrytí a Dominující množinu. Bidimensionalita - optimum problému na mřížce r x r je Ω(r²). (str. 140-146, 200-210 PA)
  Domácí úkoly:
  33. Ukažte, že následující problém je v Neuniformním FPT:
      Planar Diameter Improvement (Zlepšení průměru rovinného grafu)
      Vstup: Rovinný graf G, k nezáporné celé.
      Otázka: Existuje rovinný nadgraf G který má průměr (vzdálenost dvou nejvzdálenějších vrcholů) nejvýše k?
      (2 body)
  34. Ukažte, že následující problém je v Neuniformním FPT:
      Cycle Packing (Vkládání cyklů)
      Vstup: Graf G, k nezáporné celé.
      Otázka: Existuje v G alespoň k vrcholově disjunktních kružnic?
      (3 body)
  35. Ukažte, že Feedback Vertex Set v rovinných grafech lze řešit v čase O(2^{O(log k √ k)}n + n³). Můžete využít toho, že na grafech stromové šířky t lze Feedback Vertex Set řešit v čase O(2^{O(t log t)}n). (4 body)
  36. Najděte algoritmus, který pro zadaný graf H vyrobí MSOL formuli vyjadřující "má H jako minor". (4 body)
• 16.5. Přednáška: Parametrizovaná nedostupnost - parametrizovaná redukce; t-normalizovaná, monotonní a antimonotonní booleovská formule; váha ohodnocení; problém Vážené splnitelnosti a jeho verze, třídy W[t], W[Sat] a W[P], těžkost a úplnost, hierarchie.
  Věta o monotonním a antimonotonním kolapsu, důkaz pro Váženou antimonotonní 1-normalizovanou splnitelnost. Důsledek: Nezávislá množina (a Klika) je W[1]-úplná, Dominující množina je W[2]-úplná.
  Hypotéza exponenciálního času (ETH), implikace pro parametrizované problémy - Kliku nelze řešit v čase f(k)n^o(k), Vrcholové pokrytí obecně v 2^o(k)n^O(1) a v rovinných grafech v 2^{o(√ k)}n^O(1). Hypotéza silně exponenciálního času (SETH), implikace pro parametrizované problémy - Dominující množinu nelze řešit v čase O(n^k-ε) pro žádné k ≥ 3 a kladné ε, ani v čase (3-ε)^tw(G)n^O(1). (str. 421-426, 435-438, 467-469, 475-477, 485, 502, 509, 513, 514 PA)
  Cvičení: Vyřešeny příklady 33 a 34. Předvedeny příklady 13b) a 26-28.
  Domácí úkoly: Trvají dosud nevyřešené příklady, tj. 29-32 a 35-36.
  
  37. Ukažte, že následující problém je FPT vzhledem ke k:
      Max-Weight 3-CNF
      Vstup: Formule φ v 3-CNF, k nezáporné celé.
      Otázka: Má φ splňující ohodnocení váhy nejvýše k?
      (4 body)
  38. Ukažte, že Hitting Set je W[2]-úplná vzhledem k velikosti řešení. (3 body)
  Vyřešené příklady lze například přinést na zkoušku.

Literatura

• M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, S. Saurabh: Parameterized Algorithms (r.v. 2015) - ke stažení s univerzitním přístupem
• Textík, který se od přednášky dost liší a navíc je v angličtině
• Rodney G. Downey, M.R. Fellows: Parameterized Complexity (r.v. 1999)
• Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms (r.v 2006) - asi nejlepší
• J. Flum, M. Grohe: Parameterized Complexity Theory (r.v. 2006) - ke stažení s univerzitním přístupem
• Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity (r.v. 2013) - ke stažení s univerzitním přístupem

Anotace

Existuje řada optimalizačních problémů, pro které nejsou známy polynomiální algoritmy (např. NP-úplné problémy). Přesto je v praxi nutné takové problémy přesně řešit. Ukážeme si, že mnoho problémů lze řešit značně efektivněji, než prostým zkoušením všech řešení. Často lze nalézt společnou vlastnost (parametr) vstupů z praxe - např. všechna řešení jsou malá. Parametrizované algoritmy toho využívají tak, že jejich časová složitost je exponenciální pouze v tomto (malém) parametru, kdežto polynomiální vzhledem k délce vstupu (která může být obrovská).

Parametrizované algoritmy také představují způsob jak formalizovat pojem efektivního polynomiálního předzpracování vstupu pro těžké problémy, což v klasické výpočetní složitosti není možné. Takové polynomiální předzpracování je pak vhodným prvním krokem, ať už následně řešení hledáme libovolným způsobem.

Ukážeme si řadu metod jak parametrizované algoritmy navrhovat a zmíníme také jak ukázat, že pro jistý problém (a parametr) takový algoritmus neexistuje. Neopomineme také souvislosti s dalšími přístupy k těžkým problémům jako jsou mírně exponenciální algoritmy nebo aproximační schémata.

Přednáška je určena spíše studentům vyšších ročníků, případně i doktorandům, ale pro pochopení je nutná znalost pouze základních pojmů z teorie grafů a základů složitosti (např. BI-AG2, BI-AAG). Mohou ji tedy navštěvovat i studenti třetího ročníku bakalářského studia.

Předběžný sylabus

• Úvod. Omezené prohledávací stromy. Základní definice.
• Kernelizace jako formalizace pojmu ``efektivní předzpracování.'' Ukázky jednoduchých kernelizací.
• Prokládání kernelizace s omezenými prohledávacími stromy. Složitější prohledávací stromy.
• Kernelizace založené na globálních pravidlech.
• Neexistence polynomiálních kernelů pro některé problémy.
• Iterativní komprese. Hladové vyhledávání.
• Dynamické programovaní, využití principu inkluze a exkluze. Barevné kódování.
• Stromová šířka a základní vlastnosti.
• Dynamické programování na grafech omezené stromové šířky. Courcellova věta.
• Approximační schémata Bakerové typu.
• Minory, jejich využití ke konstrukci parametrizovaných algoritmů.
• Parametrizované algoritmy pro rovinné grafy (Bidimensionalita).
• Třídy parametrizované složitosti, parametrizované redukce, vazby na hypotézu ETH.