School of Mathematical and Computing Sciences
Victoria University of Wellington, New Zealand
4pm Tuesday 26th March 2002
Room 2511, JCMB, King's Buildings
Parameterized complexity is an attempt to try to understand the contribution of various aspects of a combinatorial problem to its overall complexity. We now see the area as a major paradigm towards the problem of paractically coping with the retical intractability. For example, although both DOMINATING SET and VERTEX COVER are NP-complete, for a fixed k, k-VERTEX COVER is solvable in time O(|G|), there seems no better algorithm for k-DOMINATING SET than trying all possibilities, taking time \Omega(n^k).
It seems appropriate, after 10 years, to look at the successes, and to articulate some of the major open questions. And perhaps to look at the claim that this might be a bit of theory that has something to say about practical computing.
The talk is intended to be relatively general.