Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Parameterized complexity : permutation patterns, graph arrangements, and matroid parameters

Tools
- Tools
+ Tools

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

[img]
Preview
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

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:
DateEvent
March 2015Submitted
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us