Exploiting New Types of Structure for Fixed Parameter Tractability (X-TRACT)

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.

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 (also called an island of tractability). Previous research has identified a large number of tractable classes for various NP-hard problems. The aim of this research project was to develop a rigorous framework for exploiting new kinds of structure on a wide range of problem inputs; in particular, this framework is based on the established notion of a modulator (or backdoor) 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 our research is fundamentally different from the structure exploited by known state-of-the-art approaches. This allows us to handle natural instances where all presently known approaches remain unfeasible. Among our results are new algorithms that apply to instances that require a large number of local changes to be placed in a known tractable class, but where these changes interact in a structured way. We applied this method successfully to the Constraint Satisfaction Problem (CSP) and generalizations of it. Other notable results apply to the area of Integer Linear Programming (ILP) which is one of the most successful computational tools used in both practical and theoretical computer science. We initiated the comprehensive study of ILP through the lens of measuring the variable interactions of the instance. We obtained a full complexity map for ILP instances whose variable interactions form a graph of bounded treewidth.