Algorithmic Meta-theorems for Restricted Classes of Graphs - Gajarský, Jakub (2016)
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 impl