# Structural Decomposition Methods and Islands of Tractability for NP-hard Problems

## Abstract

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.

## Outline

- Introduction: Computational complexity in AI; NP-hard problems Approaches for solving hard problems;
- Structural Decomposition Methods: Graph representations of problem instances; Intuition about “nearly acyclic” instances; The width parameter associated with a tractable class; Testing for membership in a tractable class; Solving an instance belonging to a tractable class;
- Identification of “easy” instances: “Early” structural decomposition approaches; Tree decomposition; Game-theoretic characterization; Meta-theorems on treewidth;
- Applications of tree decompositions: Tractability of bounded-width instances: genuine tractability; Fixed-parameter tractability; Tractability for small and large widths; Tools for proving “all-yes” instances to have small width;
- Beyond tree decompositions: The homomorphism problem: A basic recurrent problem in databases and AI; Hypergraph representations of problem instances; (Generalized) Hypertree decomposition; Fractional hypertree decompositions;The setting of tree projections;
- Algorithmic issues: Algorithms for decision problems; Algorithms for computation problems; Algorithms for computing best solutions; Enumeration and top-K computations; Applications: Game Theory, Constraint Satisfaction, Reasoning Tasks, Combinatorial Auctions;
- Recent Advances: Structural and Local Consistency Properties; Necessary and sufficient structural conditions such that local (pairwise) consistency entailsglobal (i.e. R(*,m)C) consistency in constraint satisfaction problems.

## Target

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.

The tutorial will be self-contained. No specific prerequisites are required.

## Material

- Slides
**,**Slides(3xp) **Survey Papers**

## Tutorialists

### Georg Gottlob

Gottlob is a Professor of Informatics at Oxford University, a Fellow of St John's College, Oxford, and an Adjunct Professor at TU Wien. His interests include AI, knowledge representation, logic and complexity, web data extraction, database theory, graph decomposition techniques. ottlob has received the Wittgenstein Award from the Austrian National Science Fund, is an ACM Fellow, an ECCAI Fellow, a Fellow of the Royal Society, and a member of the Austrian Academy of Sciences, the German National Academy of Sciences, and the Academia Europaea. He chaired the Program Committees of IJCAI 2003 and ACM PODS 2000, was the Editor in Chief of the Journal Artificial Intelligence Communications, and is currently a member of the editorial boards of journals, such as CACM and the Journal of Computer and System Sciences. In 2010, Gottlob was awarded an ERC Advanced Investigator's Grant for the project "DIADEM: Domain-centric Intelligent Automated Data Extraction Methodology" (see also http://diadem.cs.ox.ac.uk/). He has introduced with Nicola Leone and Francesco Scarcello the notion of hypertree width, and has been studying various aspects of graph and hypergraph-based problem decompositions for more than two decades.

### Gianluigi Greco

Gianluigi Greco is a Professor of Informatics at University of Calabria. His research ranges over different fields, across Databases and Artificial Intelligence, in particular on Database Theory, Constraint Satisfaction, Game Theory, Data Mining, and Data Integration. He has extensively published in all these areas in leading conferences and journals. He has served as a member of the program committee of more than 40 international conferences and workshops. Professor Greco has received the Marco Somalvico Award, which is annually awarded by the Italian Association for Artificial Intelligence to the young researcher that has mostly contributed to the field of Artificial Intelligence in Italy. He his co-recipient of the 2008 IJCAI-JAIR Best Paper Prize, which is annually awarded to an outstanding paper published in the Journal of Artificial Intelligence Research in the preceding five calendar years.

### Francesco Scarcello

Francesco Scarcello is a Professor of Informatics at University of Calabria. His research interests are computational complexity, graph and hypergraph theory, constraint satisfaction, logic programming, knowledge representation, non-monotonic reasoning, and database theory. He has extensively published in all these areas in leading conferences and journals. He participated in a number of national and international projects dealing with database and knowledge representation systems, such as DLV, a widely used knowledge-base management system based on disjunctive logic programming. Professor Scarcello serves on program committees and as a reviewer for many international conferences and journals. e is co-recipient of the 2008 IJCAI-JAIR Best Paper Prize, awarded to an outstanding paper published in the Journal of Artificial Intelligence Research in the preceding five calendar years. He is co-recipient of the 2009 ACM PODS Alberto O. Mendelzon Test-of-Time Award, awarded every year to a paper published in the proceedings of the ACM Symposium on Principles of Database Systems (PODS) ten years prior that had the most impact in terms of research, methodology, or transfer to practice over the intervening decade.