English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In a valued constraint satisfaction problem (VCSP), the goal is to find anassignment of labels to variables that minimizes a given sum of functions. Eachfunction in the sum depends on a subset of variables, takes values which arerational numbers or infinity, and is chosen from a fixed finite set offunctions called a constraint language. The case when all functions take onlyvalues 0 and infinity is known as the constraint satisfaction problem (CSP). Itis known that any CSP with fixed constraint language is polynomial-timeequivalent to one where the constraint language contains a single binaryrelation (i.e. a digraph). A recent proof of this by Bulin et al. gives such areduction that preserves most of the algebraic properties of the constraintlanguage that are known to characterize the complexity of the correspondingCSP. We adapt this proof to the more general setting of VCSP to show that eachVCSP with a fixed finite (valued) constraint language is equivalent to onewhere the constraint language consists of one $\{0,\infty\}$-valued binaryfunction (i.e. a digraph) and one finite-valued unary function, the latterproblem known as the (extended) Minimum Cost Homomorphism Problem for digraphs.We also show that our reduction preserves some important algebraic propertiesof the (valued) constraint language.

A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs