The main goal of this project is to develop parameterized complexity
more fully in both practical and theoretical ways. Specifically we
(1) Establish improved kernelization bounds by means of powerful
data-reduction rules for a number of combinatorial problems of central
importance. These outcomes will be based on new techniques building on
recent advances by project investigators.
(2) Devise new algorithmic strategies for polynomial-time
kernelization. As an example, we have recently established a poly(k)
kernelization strategy for the undirected feedback vertex set problem
by the novel strategy of employing a constant-factor approximation
algorithm to compute initial structure, relative to which effective
reduction rules can then be defined and applied.
(3) Develop theoretical machinery to support a mechanised
discovery and verification of data-reduction rules . Our approach is
closely related to the Myhill-Nerode methods for computing obstruction
sets in the context of well-quasi ordered sets as pioneered by
Fellows and Langston.
(4) Explore parameterized problem classes that are brought
into focus by polynomial-time preprocessing, and develop new techniques
for addressing membership issues for these classes.
A starting point for this task is the min cut linear arrangement problem.
(5) Investigate systematic ways of lateral algorithmic deployment
of parameter-specific extremal structure theory and associated polynmial-time