License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06401.3
URN: urn:nbn:de:0030-drops-8017
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/801/
Go to the corresponding Portal

Cohen, David ; Gyssens, Marc ; Jeavons, Peter

A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

pdf-format:
06401.CohenDavid.Paper.801.pdf (0.3 MB)

Abstract

In this talk (draft paper) we develop the theory of structural decompositions for the CSP. We begin with the very general notion of a guarded decomposition and make several simplifying assumptions to arrive a the definition of an acyclic guarded cover.
We show how many existing decompositions can seen as acyclic guarded covers. We develop a generic algorithm for discovering acyclic guarded covers under the further assumption that they have a join tree satisfying a simple extra condition. We show that many existing decompositions do in fact satisfy this extra condition.
Using this theory we are able to describe a new class of structural decompostion which we call spread cuts. These generalise many existing decomposition methods. We present a class of hypergraphs whose spread cut width is significantly smaller than their hypertree width.
The definition of a guarded decomposition and the algorithm for discovering them were motvated by the similar algorithms developed by Gottlob, Scarcello and Leone in their work on hypertrees. The authors also wish to acknowledge that an acyclic guarded decomposition is very similar to a generalised hypertree decomposition as described in the hypertree literature.

BibTeX - Entry

@InProceedings{cohen_et_al:DagSemProc.06401.3,
  author =	{Cohen, David and Gyssens, Marc and Jeavons, Peter},
  title =	{{A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/801},
  URN =		{urn:nbn:de:0030-drops-8017},
  doi =		{10.4230/DagSemProc.06401.3},
  annote =	{Keywords: Structural decomposition, spread cut}
}

Keywords: Structural decomposition, spread cut
Collection: 06401 - Complexity of Constraints
Issue Date: 2006
Date of publication: 15.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI