Parameterized complexity unfolds from this empirical observation as essentially a two-dimensional generalization of the familiar one-dimensional framework of P and NP. The first part of the talk will survey the basics of this relatively new framework that pits fixed-parameter tractability (FPT) as the two-dimensional analog of P, against the two-dimensional analog of NP-hardness, which is hardness for W[1]. In this framework, the first dimension (as before) is the overall input size n, and the second dimension (the parameter) k provides a way of including relevant extra structure into problem complexity analysis and algorithm design. Some structural parameters, such as bounded treewidth, have turned out to have wide practical scope, as well as mathematical depth and interest.

The connection to extremal structure theory develops in the following way. One can show that a parameterized problem is in FPT if and only if an input instance (x ,k) can be transformed in polynomial time (polynomial in both dimensions, n and k) into a decision-equivalent instance (x' ,k') that satisfies:
(1) (x' ,k') is a yes-instance if and only if (x ,k) is a yes-instance,
(2) |x'| ? g(k) for some function g(k), and
(3) k' ? k.

In this way, FPT algorithm design inevitably confronts the natural question of how powerful this polynomial time data-reduction or kernelization can be. The transformation of (x ,k) into the reduced instance (x' ,k') (the size of which depends only on the parameter k) is essentially pre-processing in polynomial time, and as such is directly exportable to useful heuristics. We are naturally interested in finding such polynomial time pre-processing algorithms where g(k) is as small as possible. Thus FPT leads inevitably to polynomial time extremal structure theory.

The second part of the talk is about a systematic approach to designing such extremal structure and kernelization algorithms. The history and recent achievements of the systematic approach will be surveyed, and the method will be illustrated by some new results on various parameterized problems.

Frances Rosamond came to the University of Newcastle from previous appointments at the University of Victoria, Canada, Victoria University in Wellington, New Zealand and was the founder of the Department of Mathematics and Natural Sciences at National University in San Diego, California and Chair of the Department for almost fifteen years. While there, she led the development of a Bachelor Degree in Mathematics, and a degree leading to California teaching certification. She organized many activities to promote the mathematical sciences to the public, including a series of AWM Kovalevskia Days. In the past five years, Dr. Rosamond has shifted into the area of theoretical computer science, especially parameterized complexity and in particular finding and proving kernelization rules, preprocessing rules that reduce the size of the original input. She received her Ph.D. from Cornell University.