Multivariate Analysis - Parameterized Complexity
CATS Tutorial on FRIDAY 3 February (Last day of ASCW Week)
This CATS tutorial offers a basic introduction to parameterized complexity theory, parameterized algorithms and applications. The multivariate perspective on complexity analysis and algorithm design has expanded rapidly in recent years, and has applications all across Computer Science where there are NP-hard problems. 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.
Multivariate complexity analysis 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 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 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 an ARC Discovery Early Career Researcher Award, ARC-PF, 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, US Office of Naval Research, NSF, Google Faculty Research, amongst other awards. At SODA 2011 there were nine papers concerning parameterized complexity & algorithms.
Any questions, please contact Frances Rosamond
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
Cost: FREE to students. Just show up on the day.
Venue: The Tutorial is part of the ACSW Week and CATS, and will be held in Melbourne at RMIT. The Friday events (CATS tutorial, 2 ACE workshops) will take place in the Storey Hall seminar rooms (aka the same place as the rest of the conference). I can't tell you exactly which such room until mid-January or so, but this narrows it down to within a few metres at most.
Go to ACSW Week
Go to CATS website