Algorithmic Meta-theorems for Restricted Classes of Graphs
Jakub Gajarský · 2016
Algoritmicke meta-věty jsou matematicka tvrzeni typu „Pro vsechny problemy vyjadřitelne v dane logice existuje efektivni algoritmus na dane třidě grafů“. Jsou důležitým nastrojem na dokazovani existence rychlých algoritmů pro těžke problemy na omezených třidach grafů. V teto praci podavame přehled znamých algoritmických meta-vět a dokazujeme několik nových meta-vět. Algoritmicke meta-věty se děli na dva typy v zavislosti na logice, pro kterou jsou urceny – algoritmicke meta-věty pro monadickou logiku druheho řadu (monadic second order logic, MSO) a algoritmicke meta-věty pro logiku prvniho řadu (first-order logic, FO). V navaznosti na toto rozliseni se tato prace sklada z dvou casti. V prvni casti se zaobira Courcellovou větou, ktera tvrdi, že pro každý problem definovatelný v logice MSO existuje linearni algoritmus na grafech s omezeným parametrem „treewidth“ a rozsiřenim teto věty na grafy s omezeným parametrem „clique width“. Největsim nedostatkem těchto výsledků je, že ackoliv implikuji existenci linearnich algoritmů pro sirokou skalu problemů, tyto algoritmy nejsou prakticky využitelne kvůli obrovským konstantam, ktere se v nich vyskytuji. V předložene praci dokazujeme, že tyto konstanty se daji vylepsit, když uvažujeme grafy s omezenými parametry „tree-depth“ a „shrub-depth“ misto „treewidth“ a „clique width“. Druha cast dizertacni prace se zaměřuje na algoritmicke věty pro logiku FO. Nejdřive podavame přehled uspěsneho a nedavno ukonceneho směru výzkumu zabývajiciho se meta-větami na řidkých grafech, pote se zaměřime na dva hlavni směry dalsiho výzkumu – meta-věty pro struktury jine než grafy a meta-věty pro huste grafy. Výzkum v oblasti meta-vět pro struktury jine než grafy byl zahajen teprve nedavno a byl zaměřen na castecně uspořadane množiny. V předkladane praci podavame důkaz nejsilnějsiho znameho výsledku v teto oblasti – dokazujeme existenci kvadratickeho algoritmu rozhodujiciho platnost formuli logiky prvniho řadu na castecně uspořadaných množinach omezene siřky. V oblasti algoritmických meta-vět pro huste grafy je největsim problemem neexistence vhodne strukturalni teorie hustých grafů. Tento problem se pokousime překonat zkoumanim třid grafů interpretovatelných v řidkých grafech a dokazujeme, že pro každý problem definovatelný v logice FO existuje efektivni algoritmus na třidach grafů interpretovatelných v grafech omezeneho stupně.