TE3: Structural Decomposition Methods and Islands of Tractability for NP-hard Problems
Tutorialists: Georg Gottlob, Gianluigi Greco & Francesco Scarcello
Monday, August 5th, morning
By focusing on the graphical structure of the underlying instances, structural decomposition methods identify islands of tractability for NP-hard problems, that is, classes of instances over which such problems can be efficiently solved. The tutorial describes the main decomposition methods proposed in the literature within a unifying framework, by focusing on computation, optimization and enumeration problems, and illustrates their applications within a number of different AI research areas, including Constraint Satisfaction, Game Theory, Combinatorial Auctions, and Reasoning on Data and Knowledge Bases.