Monday, July 13

MS6
Parameterized Complexity

10:30 AM-12:30 PM
Room: Sidney Smith 2135

This minisymposium will focus on parameterized complexity, including recent concrete complexity results and techniques, structural aspects, and open problems. The field is motivated by the many concrete problems that are NP-complete or worse, yet can be solved in polynomial time with only an additive exponential contribution from some limited distributional aspect(s) of the problem (the parameter). The theory is built around this sharper analysis of feasibility extending polynomial time and includes distinctive and powerful algorithmic techniques to exploit parameterization. It is widely embodied in practical exponential heuristics, and involves a rich and concretely applicable structure theory based on miniaturizations of Cook's and other theorems.

10:30 Parameterized Complexity, Overview and Open Questions

Rodney G. Downey, Victoria University, New Zealand

11:00 Parametric Tractability Techniques

Venkatesh Raman, The Institute of Mathematical Sciences, India

11:30 Structural Aspects of Parameterized Complexity

Kenneth W. Regan, State University of New York, Buffalo

12:00 Concrete W Hardness Results: The Challenges of Intricate Gadgeteering

Michael T. Hallett, ETH-Zentrum, Switzerland