Skip to main content

Tractable Optimization Problems through Hypergraph−Based Structural Restrictions

Georg Gottlob‚ Gianluigi Greco and Francesco Scarcello

Abstract

Several variants of the Constraint Satisfaction Problem have been proposed and investigated in the literature for modelling those scenarios where solutions are associated with some given costs. Within these frameworks computing an optimal solution is an NP-hard problem in general; yet, when restricted over classes of instances whose constraint interactions can be modelled via (nearly-)acyclic graphs, this problem is known to be solvable in polynomial time. In this paper, larger classes of tractable instances are singled out, by discussing solution approaches based on exploiting hypergraph acyclicity and, more generally, structural decomposition methods, such as (hyper)tree decompositions.

Address
Rhodes‚ Greece
Book Title
Proceedings of the 36th International Colloquium on Automata‚ Languages and Programming
Year
2009