DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2011.12

Structural Decomposition Methods and What They are Good For

Authors: Markus Aschinger, Conrad Drescher, Georg Gottlob, Peter Jeavons, and Evgenij Thorstensen

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract

This paper reviews structural problem decomposition methods, such as tree and path decompositions. It is argued that these notions can be applied in two distinct ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. Examples are given for both cases. As a new showcase for the latter usage, we report some recent results on the Partner Units Problem, a form of configuration problem arising in an industrial context. We use the notion of a path decomposition to identify and solve a tractable class of instances of this problem with practical relevance.

Cite as

Markus Aschinger, Conrad Drescher, Georg Gottlob, Peter Jeavons, and Evgenij Thorstensen. Structural Decomposition Methods and What They are Good For. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 12-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{aschinger_et_al:LIPIcs.STACS.2011.12,
  author =	{Aschinger, Markus and Drescher, Conrad and Gottlob, Georg and Jeavons, Peter and Thorstensen, Evgenij},
  title =	{{Structural Decomposition Methods and What They are Good For}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{12--28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.12},
  URN =		{urn:nbn:de:0030-drops-29960},
  doi =		{10.4230/LIPIcs.STACS.2011.12},
  annote =	{Keywords: decompositions}
}

Document

DOI: 10.4230/DagSemProc.06401.3

A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

Authors: David Cohen, Marc Gyssens, and Peter Jeavons

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

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.

Cite as

David Cohen, Marc Gyssens, and Peter Jeavons. A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.06401.3},
  URN =		{urn:nbn:de:0030-drops-8017},
  doi =		{10.4230/DagSemProc.06401.3},
  annote =	{Keywords: Structural decomposition, spread cut}
}

Search Results

Documents authored by Jeavons, Peter

Structural Decomposition Methods and What They are Good For

Abstract

Cite as

A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message