FIXED PARAMETER COMPLEXITY
Dr Ton Kloks, Department of Computer Science, Royal Holloway, University of London

Abstract: Consider an algorithm for a parameterized problem (I,k) where I is the problem instance and k the parameter. The algorithm is uniformly polynomial if it runs in time O(f(k) |I|^c) where |I| is the problem size, f(k) an arbitrary function, and c a constant. A parameterized problem is fixed-parameter tractable (FPT) if it admits a uniformly polynomial time algorithm. Parameterized complexity was introduced some 10 years ago and there are numerous algorithms known for FPT problems. A breakthrough was made with the discovery of sub-exponential (i.e., O(c^{sqrt{k}} n)) solutions for various domination problems on planar graphs. I will give an outline of the planar domination algorithm.

It was shown that finding subexponential solutions is not possible for all MAX SNP-hard problems unless W[1]=FPT. Furthermore it was shown that planar domination has no EPTAS running in time O(2^{o(sqrt{1/{epsilon}}} p(n)) unless W[1]=FPT. This indicates that the sublinear FPT solution for planar domination is `close to optimal'.

I hope there will be time to show some new results on reductions to problem kernels for some problems. For example, we showed that planar independent domination can be solved in time O(c^{sqrt{k}} + n) time. Finally I'd like to show a new algorithm solving the k-leaf spanning tree problem in time O(n+p^k) for some constant p. Hence also this solution is `close to optimal' since k-leaf spanning tree is MAX SNP-hard.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 27 June 2001.

back