Many NP-hard problems in different AI research areas are known to be efficiently solvable when restricted to instances whose underlying structures can be modeled via acyclic graphs or hypergraphs. However, structures arising from real applications are hardly precisely acyclic. Yet, they are often not very intricate and, in fact, tend to exhibit some limited degree of cyclicity, which suffices to retain most of the nice properties of acyclic ones. Therefore, several efforts have been spent to investigate invariants that are best suited to identify nearly-acyclic graph/hypergraphs, leading to the definition of a number of so-called structural decomposition methods.

The tutorial illustrates the main structural decomposition methods proposed in the literature within a unifying framework, it will discuss their game-theoretic and logical characterizations, and it presents the algorithmic approaches that can be used to efficiently solve “nearly”' acyclic instances, by looking at the so-called Methods and efficient (i.e., polynomial time) solution algorithms are presented for computation problems, where the goal is just to compute an arbitrary solution, as well as for optimization problems, where the goal is to compute the “best” solution according to some given optimization criterium. 

Moreover, approaches are also discussed which are specifically tailored to solve enumeration (and top-K) problems, where the goal is to enumerate all solutions (in fact, the top-K ones according to some given criterium) and where tractability usually means having an algorithm computing solutions with polynomial delay. As reference scenarios for the exposition, the technical tools are exemplified on problems arising in Constraint Satisfaction, Game Theory, Combinatorial Auctions, and Reasoning on Data and Knowledge Bases.

The tutorial also links recent advances in consistency properties in Constraint Satisfaction Problemes and structural properties of the (hyper)graph associated with the instances. In particular, necessary and sufficient structural conditions are described such that local (pairwise) consistency entails global (i.e. R(*,m)C) consistency in constraint satisfaction problems. 

The tutorial is intended both for academic researchers and for practitioners, wishing to familiarize with methods and algorithms tailored to efficiently solve NP-hard problems. The presentation style will be rigorously scientific and more oriented towards principles and fundamentals. We believe, in fact, that a good understanding of decomposition techniques and algorithms is highly profitable to anybody who designs or implements algorithms, and in particular for researchers interested in AI problems.

All used theoretical or mathematical concepts will be carefully introduced and illustrated. Moreover, we will highlight potential concrete applications of various methods in order to make the tutorial enjoyable for practitioners, and to stimulate cross-fertilization.