Algoritmické meta-věty jsou matematická tvrzení typu „Pro
všechny problémy vyjádřitelné v dané logice existuje efektivní
algoritmus na dané třídě grafů“. Jsou důležitým nástrojem na
dokazování existence rychlých algoritmů pro těžké problémy na
omezených třídách grafů. V této práci podáváme přehled známých
algoritmických meta-vět a dokazujeme několik nových meta-vět.
Algoritmické meta-věty se dělí na dva typy v závislosti na
logice, pro kterou jsou určeny – algoritmické meta-věty pro
monadickou logiku druhého řádu (monadic second order logic,
MSO) a algoritmické meta-věty pro logiku prvního řádu
(first-order logic, FO). V návaznosti na toto rozlišení se tato
práce skládá z dvou částí.
V první části se zaobírá Courcellovou větou, která tvrdí, že
pro každý problém definovatelný v logice MSO existuje lineární
algoritmus na grafech s omezeným parametrem „treewidth“ a
rozšířením této věty na grafy s omezeným parametrem „clique
width“. Největším nedostatkem těchto výsledků je, že ačkoliv
implikují existenci lineárních algoritmů pro širokou škálu
problémů, tyto algoritmy nejsou prakticky využitelné kvůli
obrovským konstantám, které se v nich vyskytují. V předložené
práci dokazujeme, že tyto konstanty se dají vylepšit, když
uvažujeme grafy s omezenými parametry „tree-depth“ a
„shrub-depth“ místo „treewidth“ a „clique width“.
Druhá část dizertační práce se zaměřuje na algoritmické věty
pro logiku FO. Nejdříve podáváme přehled úspěšného a nedávno
ukončeného směru výzkumu zabývajícího se meta-větami na řídkých
grafech, poté se zaměříme na dva hlavní směry dalšího výzkumu –
meta-věty pro struktury jiné než grafy a meta-věty pro husté
grafy. Výzkum v oblasti meta-vět pro struktury jiné než grafy
byl zahájen teprve nedávno a byl zaměřen na částečně uspořádané
množiny. V předkládané práci podáváme důkaz nejsilnějšího
známého výsledku v této oblasti – dokazujeme existenci
kvadratického algoritmu rozhodujícího platnost formulí logiky
prvního řádu na částečně uspořádaných množinách omezené šířky.
V oblasti algoritmických meta-vět pro husté grafy je největším
problémem neexistence vhodné strukturální teorie hustých grafů.
Tento problém se pokoušíme překonat zkoumáním tříd grafů
interpretovatelných v řídkých grafech a dokazujeme, že pro
každý problém definovatelný v logice FO existuje efektivní
algoritmus na třídách grafů interpretovatelných v grafech
omezeného stupně.