Exploiting New Types of Structure for Fixed Parameter Tractability

Funding Organisation: The Austrian Science Funds, FWF
Project Number: FWF P26696

Project Team

• Eduard Eiben
• Robert Ganian
• Ramanujan Sridharan
• Stefan Szeider (Principal Investigator)

Topic

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.