Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms

摘要

The problem of computing optimal solutions to Constraint Satisfaction Problem (CSP) instances parameterized by the size of the objective function is considered, and fixed-parameter polynomial-time algorithms are proposed within the structure-based framework of tree projections. The algorithms compute the desired optimal (or bestk) solutions whenever there exists a tree projection for the given instance; otherwise, the algorithms report that there is no tree-projection. For the case where a tree projection is available, parallel algorithms are also proposed and analyzed. Structural decomposition methods based on acyclic, bounded treewidth, and bounded generalized hypertree-width hypergraphs, extensively considered in the CSP setting, as well as in conjunctive database query evaluation and optimization, are all covered as special cases of the tree projection framework.