The Library
Parameterized complexity : permutation patterns, graph arrangements, and matroid parameters
Tools
Mach, Lukáš (2015) Parameterized complexity : permutation patterns, graph arrangements, and matroid parameters. PhD thesis, University of Warwick.
|
PDF
WRAP_THESIS_Mach_2015.pdf - Submitted Version - Requires a PDF viewer. Download (662Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b2863111~S1
Abstract
The theory of parameterized complexity is an area of computer science focusing on refined analysis of hard algorithmic problems. In the thesis, we give two complexity lower bounds and define two novel parameters for matroids.
The first lower bound is a kernelization lower bound for the Permutation Pattern Matching problem, which is concerned with finding a permutation pattern inside another input permutation. Our result states that unless a certain (widely believed) complexity hypothesis fails, it is impossible to construct a polynomial time algorithm taking an instance of the Permutation Pattern Matching problem and producing an equivalent instance of size bounded by a polynomial of the length of the pattern. Obtaining such lower bounds has been posed by Stephane Vialette as an open problem.
We then prove a subexponential lower bound for the computational complexity of the Optimum Linear Arrangement problem. In our theorem, we assume a conjecture about the computational complexity of a variation of the Min Bisection problem.
The two matroid parameters introduced in this work are called amalgam-width and branch-depth. Amalgam-width is a generalization of the branch-width parameter that allows for algorithmic applications even for matroids that are not finitely representable. We prove several results, including a theorem stating that deciding monadic second-order properties is fixed-parameter tractable for general matroids parameterized by amalgam-width. Branch-depth, the other newly introduced matroid parameter, is an analogue of graph tree-depth. We prove several statements relating graph tree-depth and matroid branch-depth. We also present an algorithm that efficiently approximates the value of the parameter on a general oracle-given matroid.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Matroids, Permutations | ||||
Official Date: | March 2015 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Král, Daniel | ||||
Extent: | 120 leaves | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year