---
title: "A Comparison of Structural CSP Decomposition Methods"
authors:
  - "Georg Gottlob"
  - "Nicola Leone"
  - "Francesco Scarcello"
doi: ""
url: "https://ijcai.org/proceedings/1999/57"
pdf: "https://ijcai.org/proceedings/1999/0057.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "394-398"
track: "Constraint Satisfaction"
keywords:
---

# A Comparison of Structural CSP Decomposition Methods

Georg Gottlob, Nicola Leone, Francesco Scarcello

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 394-398.

## Abstract

We compare tractab le classes of constraint satisfaction problems (CSPs) . We first give a uniform prese ntation of the major structural CSP decomposition m et hods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory. We introduce a framework for comparing parametric decomposition-based m et hods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general (nonbinary) CSPs.