The theory and techniques of Parameterized Complexity have become increasingly important in dealing with problems that are NP-hard or worse - as is so frequently the case in the natural world of computing. The key idea of the theory is to isolate some aspect(s) or part(s) of the input as the parameter, and to confine the seemingly inevitable combinatorial explosion of computational difficulty to an additive function of the parameter, with other costs being polynomial (problems with such solutions are said to be fixed parameter tractable, abbreviated as FPT).
An example is the NP-complete Vertex Cover problem (does the graph
have a vertex cover of size 
?) that is now solvable in less than
steps. Type-checking in ML is another example.
Although complete for EXPTIME in general, it is solved in practice in
time 
for programs of size 
where the is the nesting
depth of declarations.
The real excitement is in the rapidly developing systematic connections between FPT and useful heuristic algorithms bridging the theory of computing and computing in practice. FPT algorithms have found important use in areas like Computational Biology where small parameters seem to capture practical applications. Although many naturally parameterized problems are in FPT, some are not. The rich positive toolkit of novel techniques for designing FPT algorithms is accompanied in the theory by a corresponding negative toolkit that supports a rich theory of parametric intractability.
In this workshop, starting from a brief introduction, we hope to discuss the recent research trends and future research prospects in this area. The workshop should be of interest to researchers in algorithm design, complexity theory as well as in applied algorithmics. The list of speakers includes
During December 4th to 6th, we will have a preparatory school for the workshop, aimed towards University teachers and senior research students, who have some basic background in Algorithms design and analysis. In this school we will review various heuristics and algorithm design techniques that are useful to understand the algorithms for the parameterized problems.
Organizers: Mike Fellows (U Victoria), Meena Mahajan (IMSc Chennai), Venkatesh Raman (IMSc Chennai)
Address for Correspondence