Exploiting New Types of Structure for Fixed Parameter Tractability (Research Project)
Many important computational problems are intractable on general instances. However, realistic problem instances often contain a certain hidden structure that can be exploited to solve the problem efficiently. Such instances form a tractable class (or an island of tractability). Previous research has identified a large number of tractable classes for various NP-hard problems.
The aim of this project is to develop a rigorous framework for exploiting new kinds of structure on a wide range of problem inputs; in particular, this framework will be based on the established notion of a modulator to a tractable class of instances, which applies to problem instances that may be placed in a tractable class by a small number of local changes. The type of structure exploited by algorithms developed within the proposed research is fundamentally different from the structure exploited by known state-of-the-art approaches. This will allow us to handle natural instances where all presently known state-of-the-art approaches remain unfeasible.
|||Quantified Conjunctive Queries on Partially Ordered Sets|
Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, pages 122-134, 2014.