Efektivní algoritmy pro speciální třídy problémů

Přednáška a cvičení se bude konat v pondělí od 15:45 do 18:00 v učebně UL610 v budově FAV ZČU v Plzni (v případě obsazenosti učeby UL610, v učebně UL608). Přednáška a cvičení na sebe volně navazují a jejich časový rozsah se bude měnit dle potřeby. Na MFF UK si lze tento předmět zapsat jako NDMI076 Nové trendy v teorii grafů.

V přednášce se zaměříme na tzv. algoritmické metavěty, tj. výsledky, které zaručují existenci efektivních algoritmů pro třídy rozhodovacích problémů nebo úloh. V této souvislosti též uvedeme a dokážeme některé související poznatky zejména ze strukturální teorie grafů a logiky. Předpokládá se základní znalost teorie grafů a základů výpočetní složitosti.

Zkouška

Při zkoušce bude požadována znalost vět z přednášky (včetně důkazů) a řešení příkladů, které byly na cvičení (viz seznam níže), včetně schopnosti použít postupy vedoucí k jejich vyřešení na podobné příklady.

Literatura

• R. G. Downey, D. M. Thilikos: Confronting intractability via parameters, to appear in Computer Science Review.
• H.-D. Ebbinghaus, J. Flum: Finite model theory, Springer, 2005.
• J. Flum, M. Grohe: Parameterized complexity theory, Birkhäuser, 2006.
• M. Grohe, S. Kreutzer: Methods for Algorithmic Meta Theorems, to appear in M. Grohe, J. Makowsky (eds.), Model theoretic methods in finite combinatorics, AMS Contemporary Mathematics Series.
• R. Niedermeier: Invitation to fixed-parameter algorithms, Oxford University Press, 2006.

Obsah přednášky

Příklady ze cvičení

• Sestrojte lineární algoritmus, který rozhodne, zda zadný strom obsahuje vrcholové pokrytí velikosti k (k je na vstupu).
• Sestrojte lineární algoritmus, který určí velikost největší nezávislé množiny v zadaném stromě.
• Sestrojte lineární algoritmus, který rozhodne, zda zadaný rovinný graf obsahuje úplný graf na čtyřech vrcholech jako podgraf.
• Sestrojte lineární algoritmus, který rozhodne, zda zadaný rovinný graf obsahuje úplný graf na čtyřech vrcholech bez jedné hrany jako podgraf.
• Sestrojte lineární algoritmus, který rozhodne, zda zadaný rovinný graf obsahuje kružnici délky čtyři jako podgraf.
• Určete stromovou šířku mřížky k x k.
• Sestrojte algoritmus, který pro pevné k rozhodne v lineárním čase, zda daný graf stromové šířky k zadaný společně s hezkým stromovým rozkladem šířky k je 3-barevný.
• Sestrojte algoritmus, který pro pevné k rozhodne v lineárním čase, zda daný graf stromové šířky k zadaný společně s hezkým stromovým rozkladem šířky k je hamiltonovský.
• Vyjádřete vlastnost "být hamiltonovský" v monadické logice druhého řádu.
• Sestrojte algoritmus, který pro pevné k určí v lineárním čase seznamovou barevnost grafu stromové šířky k zadaného společně s hezkým stromovým rozkladem šířky k.
• Ukažte, že třída grafů omezeného maximálně stupně má lokálně omezenou stromovou šířku.
• Ukažte, že třída grafů vnořitelných na torus má lokálně omezenou stromovou šířku.
• Přímo ukažte, že pro každé m existuje k, že duplikátor má výherní strategii pro Ehrenfeucht-Fraissé hru s m koly pro grafy C_2k a 2C_k.
• Navrhněte FPT algoritmus, který rozhodne, zda daný graf obsahuje kružnici délky k, kde k je parametr.