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 the proposed research 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.