2009 | OriginalPaper | Buchkapitel
HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results
verfasst von : Georg Gottlob, Gianluigi Greco, Bruno Marnette
Erschienen in: Graph Theory, Computational Intelligence and Thought
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Generalized hypertree width (short:
ghw
) is a concept that leads to a large class of efficiently solvable CSP instances, whose associated recognition problem (of checking whether the
ghw
of a CSP is bounded by a constant
k
) is however known to be
NP
-hard. An elegant way to circumvent this intractability has recently been proposed in the literature, by means of a “no-promise” approach solving CSPs of bounded
ghw
without the need of actually computing a generalized hypertree decomposition. In fact, despite the conceptual relevance of this approach, its computational issues have not yet been investigated and, indeed, precise bounds on the running time of the no-promise algorithm are missing.
The first contribution of this paper is precisely to fill this gap. Indeed, the computational complexity of the no-promise approach is analyzed, by exploiting an intuitive characterization relying on the notion of
hyperconsistency width
. It turns out that, in the basic formulation, the approach is hardly suited for practical applications mainly because of its bad scaling in the size of the constraint database. Motivated by these news and based on a variant of hyperconsistency width, a different and more efficient method to decide whether CSPs of bounded
ghw
admit solutions is then provided. Importantly, the improved method exhibits the same scaling as current evaluation algorithms for instances of bounded hypertree width, nonetheless allowing to isolate a larger class of queries. Finally, to give a complete picture of the complexity issues of the no-promise approach, the problems of computing one solution and of enumerating all the solutions are also studied.