|
|
Structural and Algorithmic Properties of Permutation Classes
Opler, Michal ; Jelínek, Vít (advisor) ; Kozma, László (referee) ; Bouvel, Mathilde (referee)
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...
|
guest ::
