Efficient Pre-Processing of Hard Problems: New Approaches, Basic Theory and Applications

Partner Investigator:
Michael A. Langston, Department of Computer Science, University of Tennessee
The main goal of this project is to develop parameterized complexity more fully in both practical and theoretical ways. Specifically we seek to:
(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 reduction rules.
The Chief Investigator for this project is Vladimir Estivill-Castro at Griffith University, Queensland, Australia.
The other Partner Investigator is Michael R. Fellows at The University of Newcastle, New South Wales, Australia.