Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
This work addresses the challenge of efficiently solving optimization problems in constraint satisfaction for researchers and practitioners, but it is incremental as it builds on known tractable instances based on graph acyclicity.
The paper tackles the NP-hard problem of computing optimal solutions in cost-based Constraint Satisfaction Problem variants by identifying larger classes of tractable instances through hypergraph acyclicity and structural decomposition methods, resulting in polynomial-time solvability for these expanded classes.
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.