High-Order Consistency in Valued Constraint Satisfaction

ISSN： 1383-7133

Source： Constraints, Vol.10, Iss.3, 2005-07, pp. : 283-305

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.