This CATS Tutorial offers a basic introduction to parameterized complexity theory, parameterized algorithms and applications. There will be examples across many fields; such as, massive parallel processing of huge data sets, computational biology, computational vision, AI, and computational social choice. There will be Open Problems for good thesis projects. In addition to the basics, recent developments, such as lower bound techniques for FPT kernelization will be discussed. The parameterized complexity research community is strongly interdisciplinary, with great promise for further interdisciplinary opportunities. We look forward to welcoming many researchers/students to the Tutorial.
In multivariate complexity analysis, one considers the effect on problem complexity of secondary measurements beyond the overall input size n. The central notion of fixed parameter tractability is a generalization of polynomial time based on confining any non-polynomial (typically exponential) complexity costs to a function only of these secondary measurements. Parameterized algorithms have strong connections to heuristics for NP-hard problems, and the multivariate approach allows more realistic modeling of real-world input distributions.
Take for an example the data cleaning problem: We have n data samples from some physical experiment. Due to measurement errors some data points make no sense. To be more precise: there can be pairs of data points that contradict each other. The goal is to delete as few data points as possible to get rid of all conflicts. As a parameterized problem we can state this as follows: The input consists of n data points and a number k the parameter. The question is whether we can delete up to k data points to make the data consistent.
In practice n can be very big, but we expect k to be much smaller. This problem is NP-complete, but we can easily find an algorithm that runs in time O(2k + n).
++ABOUT THE FIELD++
The Parameterized Complexity Newsletter is archived at *http://fpt.wikidot.com**. The newsletter and the wiki give history and recent developments in the field and should be consulted for background material for the tutorial. Recent conference papers and papers on arXiv are located on the wiki.
The field has generated well over 10 million Euros in research funding in the past two years, including two Starting Grants and one Advanced Grant from the European Research Council, the President of Ireland Young Researcher Award of more than half a million Euro over a four year period, two Large Norwegian grants an ARC Discovery Early Career Researcher Award, ARC-PF, a US Office of Naval Research, NSF, Google Faculty Research, amongst other awards. At SODA 2011 there were nine papers concerning parameterized complexity & algorithms.
++PRESENTERS++ (There may be more)
Michael Fellows, Charles Darwin Univ., Au
Franz Brandenburg, Univ. Passau, Germany
Ljiljana Brankovic, Univ. Newcastle, Au
Michael Langston, Univ. Tennessee and Oak Ridge National Laboratory, USA
Gabor Erdelyi, Univ. Siegen, Germany
1. Introduction and basic definitions
* Why parameterized complexity?
* The “art of parameterization”
* Parameterized complexity classes
* Exponential time hypothesis
* Parameterized reductions
2. FPT algorithm design
* Bounded search trees
* Greedy localization
* Color coding
* Tree and path decompositions
* Graph minors and wqo's
* Courcelle's theorem
* Iterative compression
The Tutorial is part of the ACSW Week and CATS, and will be held in Melbourne at RMIT.
Register at the CATS website.
The venue for the CATS tutorial will be Building 10 level 08 room 03. This is not in the main conference venue, but is not far away (main conference venue is building 16 on the attached map, tutorial venue is building 10).
Any questions, please contact Frances Rosamond