Mach, Lukáš (2015) Parameterized complexity : permutation patterns, graph arrangements, and matroid parameters. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Mach_2015.pdf - Submitted Version - Requires a PDF viewer. Download (662Kb) | Preview

Request Changes to record.

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 or Dissertation (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:	Date Event March 2015 Submitted
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