Structural and Algorithmic Properties of Permutation Classes

Abstract

V této práci studujeme vztah mezi strukturou dědičných permutačních tříd a výpo- četní složitostí různých rozhodovacích problémů. Nejdříve zkoumáme strukturu permu- tačních tříd z pohledu několika různých parametrů, zejména stromové šířky. Definujeme nové vlastnosti obecné permutační třídy C, z nichž nejdůležitější je vlastnost dlouhé cesty. Z těchto vlastností pak odvodíme různé dolní odhady na to jakou největší stromovou šířku může mít permutace délky n z třídy C. Například dokážeme, že libovolná třída s vlastností dlouhé cesty má stromovou šířku neomezenou. Hlavní rozhodovací problém, kterým se zabýváme, je znám jako Permutation Pat- tern Matching (PPM). Vstupem pro problém PPM je dvojice permutací τ (text) a π (vzor), a cílem je rozhodnout jestli τ obsahuje π jako podpermutaci. Nejdříve zběžně uvažujeme problém PPM ve své obecné verzi, a poté se zaměříme na jeho variantu C- Pattern PPM, kde navíc požadujeme, aby vzor π pocházel z pevně dané třídy C. Za předpokladu různých strukturálních vlastností třídy C pak odvodíme jak klasické tak pa- rametrizované těžkostní výsledky. Například ukážeme, že problém C-Pattern PPM je NP-úplný kdykoliv třída C má vlastnost dlouhé cesty. Dále se zaměříme na ještě více omezenou variantu problému PPM, ve které požadu- jeme, aby i text pocházel z pevně dané třídy C. Tento...

In this thesis, we study the relationship between the structure of permutation classes and the computational complexity of different decision problems. First, we explore the structure of permutation classes through the lens of various parameters, with a particular interest in tree-width. We define novel structural properties of a general permutation class C, the most notable being the long path property. Using these properties, we infer lower bounds on the maximum tree-width attained by a permutation of length n in C. For example, we prove that any class with the long path property has unbounded tree-width. The main decision problem we consider is known as Permutation Pattern Match- ing (PPM). The input of PPM consists of a pair of permutations τ (the 'text') and π (the 'pattern'), and the goal is to decide whether τ contains π as a subpermutation. Af- ter briefly considering general PPM, we focus on its pattern-restricted variant known as C-Pattern PPM where we additionally require that the pattern π comes from a fixed class C. We derive both classical and parameterized hardness results assuming different structural properties of C. For example, we show that C-Pattern PPM is NP-complete whenever C has the long path property. Furthermore, we focus on an even more restricted variant of PPM where the text is...