Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring

Valued constraint satisfaction problems with ordered variables (VCSPO) are a special case of Valued CSPs in which variables are totally ordered and soft constraints are imposed on tuples of variables that do not violate the order. We study a restriction of VCSPO, in which soft constraints are imposed on a segment of adjacent variables and a constraint language Γ consists of { 0, 1} -valued characteristic functions of predicates. This kind of potentials generalizes the so-called pattern-based potentials, which were applied in many tasks of structured prediction. For a constraint language Γ we introduce a closure operator, Γ^∩¯ ⊇ Γ , and give examples of constraint languages for which | Γ^∩¯ | is small. If all predicates in Γ are cartesian products, we show that the minimization of a generalized pattern-based potential (or, the computation of its partition function) can be made in O(| V| · | D| ²· | Γ^∩¯ | ²) time, where V is a set of variables, D is a domain set. If, additionally, only non-positive weights of constraints are allowed, the complexity of the minimization task drops to O(| V| · | Γ^∩¯ | · | D| · max_ϱ∈Γ‖ ϱ‖ ²) where ‖ ϱ‖ is the arity of ϱ∈ Γ . For a general language Γ and non-positive weights, the minimization task can be carried out in O(| V| · | Γ^∩¯ | ²) time. We argue that in many natural cases Γ^∩¯ is of moderate size, though in the worst case | Γ^∩¯ | can blow up and depend exponentially on max_ϱ∈Γ‖ ϱ‖ .