Parametrizované algoritmy a složitost, letní semestr 2010

Přednáška se z technických důvodů koná jako "Vybrané kapitoly z teorie grafů - NDMI070". Přednášející Ondřej Suchý.
Přednáška se koná v úterý od 10.40 na chodbě KAMu, 2.patro malostranské budovy.

Anotace, Obsah přednášky, Literatura, Probraná témata

Probraná témata

• 1.3.- úvod, ukázky - rešitelnost SATu vzhledem k různým parametrům, prohledávací strom pro Multiřez Stromu; základní definice - parametrizovaný problém, třída FPT, třída XP; ekvivalence definic s O(f(k) * n^c) a s O(f'(k) + n^c')
• 8.3.- zmíňka o těžkých parametrizovaných problémech (třídy W[1]...klika, W[2]...dominující množina), bez jakýchkoliv detailů, definic, apod.; Kernelizace (Datová redukce, redukce dat, redukce na jádro problému) - Bussova redukce pro Vrcholové pokrytí (odstraň izolované vrcholy a "použij" vrcholy velkého stupně - O(k^c') kernel), formální definice, kernel o O(k²) vrcholech pro Editování Clusterů (nedodělalo se)
• 16. a 23.3. - hodina odpadla
• 30.3. - dokončení kernelu pro Editování Clusterů, triviální kernel o 4k vrcholech pro Nezávislou množinu v rovinných grafech, koruny v grafu a kernel o 3k vrcholech pro Vrcholové Pokrytí, Kernel o 2k vrcholech pro vrcholove pokrytí založený na párování (Nemhauser-Trotter)(bez důkazu)
• 6.4. - omezené prohledávací stromy: hlavní myšlenka, prohl. stromy pro Vrcholové pokrytí - jednoduchý 2^k strom, pokus o složitější 1,381^k strom (ukázali jsme pouze 1.466^k); 6^k pro nezávislou množinu v rov. grafech; 3^k a 2,27^k stromy pro Editování Clusterů; Zmíňka o Dominující Množině v rovinných grafech
• 13.4. - Dynamické programování: pseudopolynomiální algoritmy jsou vlastně také parametrizované - připomenutí Batohu, O(3^k.n+2^k.n² + n².log n + n.m) algoritmus pro Steinerův strom (k...počet terminálů) (Dreyfuss, Wagner) jak to zrychlit (jen se zmínilo); Barevné kódování - 2^O(k).m.log n algoritmus pro k-Cestu; rozhodnout, zda H je podgraf G lze v čase 2^O(|V(H)|).|V(G)|^tw(H)+1.log |V(G)|, kde tw(H) je stromová šířka H (bez důkazu).
• 20.4. - Iterativní komprese - pro Vrcholové Pokrytí, pro Bipartizaci Grafu(4 strany včetně úvodu do IK); Hladové vyhledávání - pro Dělení Množin, pro Pakování 3-Množin.
• 20.4. (pro zájemce) odpoledne na průnikáčích - Nezávislá množina v d-Dir (kombinace skoro kernelizace a hladového vyhledávaní)
• 27.4. - Opakování z NDMI077: Stromová šířka, Kliková šířka, ..., MSOL1,MSOL2, Courcelova věta pro Stromovou a Klikovou šířku, Minory, Minory jsou dobré quasiuspořádání, Testovat, zda H je minor G lze v O(f(H).n³) - vše bez důkazu(Přehledový článek), Rozpoznat třídu vzdálenou k vrcholů od třídy uzavřené na minory lze v neuniformním FPT - Př.: k-Apex grafy, Feedback Vetex Set, Vrcholové pokrytí, Rozpoznávání zda lze graf modifikovat (přidáním i hran, smazáním j hran a k vrcholů) aby spadl do dědičné třídy charakterizované konečně mnoha zak. ind. podgrafy lze v FPT vzhledem k (i,j,k);
  Bidimensionalita- má-li rovinný graf velkou stromovou šířku, obsahuje velkou mřížku jako minor a velkou částečně triangulovanou mřížku jako kontrakci (bez dk) - odtud O(2^O(√k)n) "Win/Win" algoritmus pro Vrcholové pokrytí a Dominující množinu v rovinných grafech (oba s dk); "Win/Win" algoritmus pro k-Listovou kostru (taky s dk).
• 4.5. - Tři algoritmické výsledky pro problémy parameterizované velikostí vrcholového pokrytí grafu (článek): Rozšiřování částečného obarvení (FPT - kernelizace), Vyrovnané barvení (FPT - převod na Celočíselné lineární programování, které je FPT vzhledem k počtu proměnných), Přiřazení kanálů (XP algortimus založený na zkoumání všech "scénářů" řešení); (přednášel Prof. Kratochvíl)
• 11.5. - Parametrizovaná složitost: základní definice - parametrizovaná redukce, t-Normalizovaná booleovská formule, Vážená t-Normovaná Splnitelnost, třídy W[t], W[Sat], W[P], těžkost a úplnost pro ně; Věta o monotónním/antimonotónním kolapsu (bez dk) důkaz, že Vážená Antimonotónní q-CNF splnitelnost je W[1]-úplná pro každé pevné q, odtud Klika,Nezávislá množina a Mnohobarevná klika jsou W[1]-úplné.
• 18.5. - dokončení složitosti - ukázky redukcí (Silně souvislý Steinerův podgraf, Listové Barvení vzhledem k vc); Para-NP-úplnost, charakterizace pomocí Turingovských strojů, vazby na hypotézu ETH (Slajdy od D. Marxe), neexistence polynomiálních jader - věta a příklad použití na k-Cestu (učebnice od D. Lokshtanova a S. Saurabha)

Anotace

Existuje řada optimalizačních problémů, pro které nejsou známy polynomiální algoritmy (např. NP-úplné problémy). Přesto je často v praxi nutné takové problémy přesně řešit. Ukazuje se, že řadu problémů lze řešit mnohem efektivněji, než prostým zkoušením všech řešení. Často lze nalézt společnou vlastnost (parametr) vstupů z praxe (kterou vstupy z NP-úplnostních důkazů nemají) - 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 (stále stejně) polynomiální vzhledem k délce vstupu (která může být obrovská). Jejich časová složitost je tedy O(f(k)*n^c), kde c je konstanta a f libovolná funkce (narozdíl od často triviálních O(n^g(k))).

Základy oboru položili Downey a Fellows ve své knize z roku 1999 (viz literatura), od té doby se obor prudce rozvíjel a v současnosti je tento obor stále populárnější.

Ukážeme si jak parametrizované algoritmy navrhovat a také jak ukázat, že pro jistý problém (a parametr) takový algoritmus neexistuje.

Přednáška je určena především studentům vyšších ročníků, případně i doktorandům. Předpokládá se znalost základních pojmů z teorie algoritmů (např. DMI026). Přednášející v tomto oboru pracuje a publikuje.

Obsah přednášky

1. Výhody parameterizovaných algoritmů proti jiným způsobům řešení těžkých problémů
2. Základní definice-parametrizovaný problém, třídy FPT, XP
3. Metody návrhu parameterizovaných algoritmů (s příklady na grafových problémech):
   1. Datové redukce, jádro (kernel) problému a jeho význam pro celou teorii
   2. Omezený prohledávací strom, analýza jeho velikosti, prokládání
   3. Dynamické programování
   4. Barevné kódování
   5. Celočíselné lineární programování
   6. Iterativní komprese, hladové vyhledávání,
   7. Dobrá quasiuspořádání, Stromové rozklady apod. - spíše zmíňka, více viz Algoritmy pro specifické třídy grafů - NDMI077
   8. Bidimensionalita
4. Parametrizovaná složitost - parametrizované redukce, třídy složitosti W[1], W[2], úplné problémy, důkazy neexistence polynomiálních jader.

Literatura

• R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006. - novější, velmi čtivá kniha, pokrývá téměř všechna probíraná témata, ale bohužel v MFF knihovně není
• M. R. Fellows and R. G. Downey: Parameterized Complexity, Springer-Verlag, 1999. - několik výtisků je i v knihovně, ale kniha je poněkud staršího data, takže chybí některé novější metody a je méně čtivá.
• Disertační práce D. Lokshtanova
• Slajdy k podobné přednášce od R. Niedermeiera a J.Gua
• FPT wiki
• Poznámky z doktorandské školy o parametrizovaných a exponenciálních algoritmech - pro účely přednášky asi nejzajímavějši poznámky od D. Marxe, částečně M.Fellowse, D.Lokshtanova a S. Saurabha, případně F. Fomina