Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms (Q935141): Difference between revisions

The authors study the valued constraint satisfaction problem (VCSP), an instance of which is the tuple \(\mathcal{P}=(V, D, C)\) where - \(V\) is a finite set of variables, - \(D\) is a finite set of possible \textit{values}, - \(C\) is a set of valued constraints of the kind \(c=(\sigma,\phi)\) with \(\sigma\) a tuple of variables, the scope of \(c\), and \(\phi: D^{| \sigma| } \rightarrow \mathbb{R}_{+} \cup \{\infty\}\), the cost function of \(c\). (VCSP) provides a general framework for a variety of combinatorial optimization problems including MAX-SAT, MAX-CSP, MIN-ONES SAT or MIN-COST HOMOMORPHISM. Valued constraints, for which an optimal solution of (VCSP) can be obtained in polynomial time, are called tractable. The purpose of this paper is to describe a large family of tractable valued constraint classes, which include submodular functions and Horn clauses as special cases. To this end the authors introduce the notion of a tournament operation and show that any set of valued constraints associated with an arbitrary pair of tournament operations defines a tractable optimization problem.