Funding: George Osipov: Supported by the Swedish Research Council (VR) under grant 2024-00274. Paweł Rzążewski: Supported by the National Science Centre grant 2024/54/E/ST6/00094. Stanislav Živný: Supported by UKRI EP/X024431/1.
Introduction
Constraint Satisfaction Problems (CSPs) and their extensions provide a broad framework encompassing many fundamental algorithmic problems. The Valued Constraint Satisfaction Problem (VCSP) extends this framework to optimization problems. Let D D D be a finite nonempty domain. A cost function of arity a a a is a function f : D a → Q ≥ 0 ∪ { ∞ } f : D^a \to\mathbb{Q}_{\ge0} \cup\{\infty\} f : D a → Q ≥ 0 ∪ { ∞ } . For a fixed finite domain D D D and a finite set Γ \Gamma Γ of cost functions, an instance of VCSP(Γ \Gamma Γ ) consists of a finite set V V V of variables and a finite family C \mathcal{C} C of constraints. Each constraint C ∈ C C \in\mathcal{C} C ∈ C is a triple ( f , S , w ) (f,S,w) ( f , S , w ) , where f ∈ Γ f \in\Gamma f ∈ Γ is the cost function, denoted by cost f ( C ) \operatorname{cost}_f(C) cost f ( C ) , S ∈ V arity ( f ) S \in V^{\operatorname{arity}(f)} S ∈ V arity ( f ) is a tuple of arity ( f ) \operatorname{arity}(f) arity ( f ) variables, and w ∈ Q > 0 w \in\mathbb{Q}_{>0} w ∈ Q > 0 is a positive rational weight. The goal is to find an assignment of values to variables that minimizes the total weighted cost of all constraints in C \mathcal{C} C .
Over the past decades, considerable effort has been devoted to characterizing the sets Γ \Gamma Γ for which VCSP(Γ \Gamma Γ ) is polynomial-time solvable. If every f ∈ Γ f \in\Gamma f ∈ Γ takes values in { 0 , ∞ } \{0,\infty\} { 0 , ∞ } , that is, if every constraint is crisp, then VCSP(Γ \Gamma Γ ) reduces to a decision problem whose goal is to find a feasible assignment. The Feder–Vardi Dichotomy Conjecture [41 ] , proved by Bulatov [10 ] and Zhuk [Zhu20] independently, states that every such problem is either polynomial-time solvable or NP-hard. For the case where every f ∈ Γ f \in\Gamma f ∈ Γ is finite-valued, a dichotomy theorem was proved by Thapper and Živný [79 ] . Finally, the combination of the work by Kozik and Ochremiak [51 ] and by Kolmogorov, Krokhin, and Rolínek [49 ] unified these results by establishing a dichotomy for every fixed finite constraint language Γ \Gamma Γ : VCSP(Γ \Gamma Γ ) is either polynomial-time solvable or NP-hard. The search for such dichotomy theorems can be viewed as a systematic search for all relevant algorithmic ideas: a dichotomy theorem identifies a collection of algorithmic techniques and shows that, when none of them applies, no further technique can yield a polynomial-time algorithm, unless P = NP.
For each fixed Γ \Gamma Γ , the dichotomy proofs mentioned above either establish tractability or show that the problem is at least as hard as a known NP-hard problem, such as 3-Coloring or Max Cut. This suffices to distinguish polynomial-time solvable cases from NP-hard ones, but does not provide a finer understanding of the complexity of the hard cases. Intuitively, a problem equivalent to 100-Coloring should be considered harder than one equivalent to 3-Coloring: on k k k variables, the former has a search space of size 100 k 100^k 10 0 k , compared with 3 k 3^k 3 k for the latter. This distinction is invisible from the perspective of polynomial-time solvability versus NP-hardness, since 100-Coloring and 3-Coloring are polynomial-time equivalent. However, in some settings, differences of this kind can be established rigorously. One such setting is the parameterized complexity of problems on graphs of bounded treewidth.
Treewidth. Treewidth is a combinatorial graph parameter that plays a central role in graph structure theory, most prominently in the Graph Minors project of Robertson and Seymour (see, e.g., [72 , 73 , 74 ] ). From an algorithmic perspective, treewidth measures how close a graph is to being a tree, and hence how effectively the bottom-up dynamic programming techniques used for trees can be extended to it. Many applications in parameterized complexity, approximation-scheme design, and other areas rely crucially on the efficient solvability of problems on graphs of bounded treewidth [25 , 7 , 30 CFK⁺15, 67 ] . In particular, given a tree decomposition of width tw \operatorname{tw} tw , several fundamental problems can be solved in time c tw ⋅ n O ( 1 ) c^{\operatorname{tw}} \cdot n^{O(1)} c tw ⋅ n O ( 1 ) for some constant c > 1 c > 1 c > 1 using fairly standard dynamic programming. A natural goal is to determine the smallest possible value of c c c for each problem.
A line of research initiated by Lokshtanov, Marx, and Saurabh [63 ] showed that many known algorithms are optimal in the following sense: a problem can be solved in time c tw ⋅ n O ( 1 ) c^{\operatorname{tw}} \cdot n^{O(1)} c tw ⋅ n O ( 1 ) , but, assuming the Strong Exponential-Time Hypothesis (SETH) [47 , 18 ] , no algorithm runs in time ( c − ε ) tw ⋅ n O ( 1 ) (c-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} ( c − ε ) tw ⋅ n O ( 1 ) for any ε > 0 \varepsilon> 0 ε > 0 . Recent preprints by OpenAI [69 ] and Claude (Anthropic) [21 ] report refutations of the Exponential Time Hypothesis (ETH), and hence also refutations of SETH. However, many of the lower bounds developed over the years remain valid under the weaker conjecture CNF-SETH — that is, n n n -variable m m m -clause SAT with unbounded clause size cannot be solved in time ( 2 − ε ) n ⋅ ( n + m ) O ( 1 ) (2-\varepsilon)^n \cdot(n+m)^{O(1)} ( 2 − ε ) n ⋅ ( n + m ) O ( 1 ) for any ε > 0 \varepsilon> 0 ε > 0 — which has not been refuted as of this writing. Prior work [48 , 58 , 60 ] introduced the even weaker Primal Pathwidth Strong Exponential Time Hypothesis (pw-SETH) and Primal Treewidth Strong Exponential Time Hypothesis (tw-SETH), and showed that they also form a source of hardness for these lower bounds and are in some cases actually equivalent to them. Both of these hypotheses follow from CNF-SETH. For some problems, these lower bounds establish the optimality of straightforward dynamic programming, whereas for others, achieving the optimal base c c c requires nontrivial algorithmic ideas. For a broad range of tight treewidth and pathwidth bounds, including counting variants, and results on the hypotheses underlying these bounds, see [63 vRBvL⁺18, CNP⁺22, 48 , 8 KLP22, 36 , 20 , 22 , 70 , 32 , 68 , 33 , 39 FMM⁺25a, FMM⁺25b] . [65 , 35 , 58 , 59 , 60 ] . The primal graph (or Gaifman graph) of a VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) instance has the variables as its vertices, with two vertices adjacent if the corresponding variables occur together in some constraint. Given a VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) instance and a tree decomposition of width tw \operatorname{tw} tw of its primal graph, standard dynamic programming solves the instance in time ∣ D ∣ tw ⋅ n O ( 1 ) |D|^{\operatorname{tw}} \cdot n^{O(1)} ∣ D ∣ tw ⋅ n O ( 1 ) . Is this running time optimal for every Γ \Gamma Γ for which VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) is NP-hard? For some languages Γ \Gamma Γ , simple improvements are possible, for example when two values a , b ∈ D a,b \in D a , b ∈ D play exactly the same role in every cost function of Γ \Gamma Γ . This raises the possibility that less obvious algorithmic ideas could lead to further improvements. Ideally, for every finite Γ \Gamma Γ for which VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) is NP-hard, we would like to identify a constant c Γ > 1 c_\Gamma> 1 c Γ > 1 , give an algorithm running in time c Γ tw ⋅ n O ( 1 ) c_\Gamma^{\operatorname{tw}} \cdot n^{O(1)} c Γ tw ⋅ n O ( 1 ) , and prove a conditional lower bound ruling out running time ( c Γ − ε ) tw ⋅ n O ( 1 ) (c_\Gamma-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} ( c Γ − ε ) tw ⋅ n O ( 1 ) for every ε > 0 \varepsilon> 0 ε > 0 .
An important step toward the CSP and VCSP dichotomies was the resolution of their conservative cases [9 , 57 ] . The term conservative has been used with somewhat different meanings in the CSP and VCSP literature. For the decision problem CSP ( Γ ) \operatorname{CSP}(\Gamma) CSP ( Γ ) , conservativity means that, for every subset S ⊆ D S \subseteq D S ⊆ D , a constraint restricting a variable to S S S is available. Equivalently, one may consider the list version of the problem, in which every variable v v v is equipped with a “hard list” L v ⊆ D L_v \subseteq D L v ⊆ D , and the goal is to find a solution respecting all these lists. In our setting, this means that Γ \Gamma Γ contains every unary { 0 , ∞ } \{0,\infty\} { 0 , ∞ } -valued cost function. In the VCSP literature, on the other hand, conservativity means that every finite-valued unary cost function is considered to be available. Equivalently, for each a ∈ D a \in D a ∈ D , the unary cost function that takes value 1 1 1 on a a a and 0 0 0 on D ∖ { a } D \setminus\{a\} D ∖ { a } is available. This can be interpreted as allowing a “soft list” for each variable, specifying a cost c v , d c_{v,d} c v , d for assigning value d d d to variable v v v .
Main result. Our main result determines c Γ c_\Gamma c Γ when Γ \Gamma Γ allows hard lists (that is, contains every unary { 0 , ∞ } \{0,\infty\} { 0 , ∞ } -valued cost function) and all its other cost functions are finite-valued. We call such a language a finite-valued hard-list language . Let pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) be the set of all cost functions that can be obtained from finite weighted sums of constraints from Γ \Gamma Γ by minimizing over auxiliary variables and allowing an additive rational shift. Let c Γ c_\Gamma c Γ be the size of the largest set S ⊆ D S \subseteq D S ⊆ D such that pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains the binary disequality function on S S S : that is, there is a function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) such that g ( x , x ) = 1 g(x,x)=1 g ( x , x ) = 1 for every x ∈ S x \in S x ∈ S and g ( x , y ) = 0 g(x,y)=0 g ( x , y ) = 0 for every x , y ∈ S x,y \in S x , y ∈ S , x ≠ y x \ne y x = y . Note that in our context, we can always make g g g have infinite or very large value outside S S S .
Theorem 1.1. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite-valued hard-list language over D D D .
(1) There is an algorithm that, given a VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) instance I I I together with a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , solves I I I in time
( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (c_\Gamma)^{\operatorname{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)}. ( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (2) If c Γ ≥ 2 c_\Gamma\ge2 c Γ ≥ 2 , for every ε > 0 \varepsilon> 0 ε > 0 , there is no algorithm that solves an instance I I I of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , given together with a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , in time
( c Γ − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (c_\Gamma-\varepsilon)^{\operatorname{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)}, ( c Γ − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , unless tw \operatorname{tw} tw -SETH is false. The same lower bound holds under pw \operatorname{pw} pw -SETH with treewidth replaced by pathwidth.
As CNF-SETH implies both tw \operatorname{tw} tw -SETH and pw \operatorname{pw} pw -SETH, these results are also true under CNF-SETH. An example deferred to Appendix A clarifies a delicate detail in the definition of c Γ c_\Gamma c Γ and the statement of Theorem 1.1. It is not necessarily true that restricting every relation in Γ \Gamma Γ to the set S ⊆ D S \subseteq D S ⊆ D yields a language Γ S \Gamma_S Γ S with the same complexity: in fact, there is a language Γ \Gamma Γ such that even though VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) requires ∣ S ∣ tw ⋅ n O ( 1 ) |S|^{\operatorname{tw}} \cdot n^{O(1)} ∣ S ∣ tw ⋅ n O ( 1 ) time for some S ⊆ D S \subseteq D S ⊆ D , for each S ′ ⊆ D S' \subseteq D S ′ ⊆ D the problem obtained by restricting Γ \Gamma Γ to S ′ S' S ′ is even polynomial-time solvable. It is possible that in order to express the disequality function on S S S appearing in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , we need to rely on values outside S S S . For example, it is possible that the optimum running time is 2 tw ⋅ n O ( 1 ) 2^{\operatorname{tw}} \cdot n^{O(1)} 2 tw ⋅ n O ( 1 ) , but restricting the domain to every subset of size two gives a polynomial-time solvable problem.
The lower bound of Theorem 1.1(2) follows fairly easily from the way c Γ c_\Gamma c Γ is formulated. A binary disequality function over a domain S ⊆ D S \subseteq D S ⊆ D of size ∣ S ∣ ≥ 3 |S| \ge3 ∣ S ∣ ≥ 3 can be used to express ∣ S ∣ |S| ∣ S ∣ -COLORING: replacing each edge with such a constraint, the optimum value is 0 0 0 if and only if the graph has an ∣ S ∣ |S| ∣ S ∣ -coloring. It has been established in earlier work [58 , 60 ] that q q q -COLORING for q ≥ 3 q \ge3 q ≥ 3 has no ( q − ε ) tw ⋅ n O ( 1 ) (q-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} ( q − ε ) tw ⋅ n O ( 1 ) time algorithm for any ε > 0 \varepsilon> 0 ε > 0 (assuming tw \operatorname{tw} tw -SETH, similarly for pathwidth under pw \operatorname{pw} pw -SETH). For ∣ S ∣ = 2 |S|=2 ∣ S ∣ = 2 , we can use a similar reduction from MAX CUT, for which lower bounds are also known [60 , 58 , 48 , 35 ] . Therefore, the majority of the proof is devoted to the upper bound of Theorem 1.1(1): showing that there are algorithmic ideas that allow us to reduce the running time precisely to ( c Γ ) t w ⋅ n O ( 1 ) (c_{\Gamma})^{\mathrm{tw}} \cdot n^{O(1)} ( c Γ ) tw ⋅ n O ( 1 ) . That is, we need to make a connection between c Γ c_{\Gamma} c Γ , which was defined by existence of cost functions in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , and the existence of algorithmically exploitable structural properties of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) .
Soft lists. Let Γ \Gamma Γ be a finite-valued language that allows all soft lists (that is, contains every unary { 0 , 1 } \{0,1\} { 0 , 1 } -valued cost function that takes value 1 on exactly one element of D D D ). We call such a language a finite-valued soft-list language . Let Γ ′ \Gamma' Γ ′ be the extension of Γ \Gamma Γ to a finite-valued hard-list language by introducing every { 0 , ∞ } \{0,\infty\} { 0 , ∞ } -valued unary cost function. It is easy to see that VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) and VCSP ( Γ ′ ) \operatorname{VCSP}(\Gamma') VCSP ( Γ ′ ) have essentially the same complexity: hard lists can be simulated by imposing sufficiently large finite penalties on excluded values. Thus, applying Theorem 1.1 to Γ ′ \Gamma' Γ ′ yields a precise complexity characterization for every finite-valued soft-list language Γ \Gamma Γ . In particular, our result refines the polynomial-time versus NP-hard dichotomy of Kolmogorov and Živný [57 ] for finite-valued conservative VCSP by determining the optimal base of the exponent in the NP-hard cases. We can therefore distinguish between the complexities of different NP-hard cases of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) .
As we shall see, both the optimal algorithm and the value of c Γ c_{\Gamma} c Γ are significantly easier to describe for finite-valued soft-list languages: in the NP-hard cases, c Γ c_{\Gamma} c Γ is exactly the number of equivalence classes under a relation called additive equivalence. Accordingly, we organize the proof by first establishing the result for finite-valued soft-list languages and then building on it to prove Theorem 1.1 for finite-valued hard-list languages. Much of the technical difficulty in the hard-list setting lies in expressing all soft lists on a certain subset of the domain D D D .
Comparison with graph homomorphisms. A special case of Theorem 1.1 was established by Esmer et al. [35 ] in their study of the Edge-Deletion List Homomorphism problem.1 In our terminology, this corresponds to the case where, apart from the hard-list functions, Γ \Gamma Γ contains only a single finite-valued cost function, which is binary, symmetric, and { 0 , 1 } \{0,1\} { 0 , 1 } -valued. Even in this restricted setting, obtaining the optimal base of the exponent requires several nontrivial algorithmic ideas:
Incomparability. If distinct values a a a and b b b both belong to the list of a variable and a a a is always at least as good as b b b (that is, a a a dominates b b b ), then b b b can be removed from that list. Therefore, we may assume that the values allowed by the hard list of each variable are pairwise incomparable (that is, no value dominates another). Consequently, the size of each list is bounded by the maximum number of pairwise incomparable values. This allows us to improve the running time of the standard dynamic programming algorithm by replacing the size of the domain with this potentially smaller bound in the base of the exponent.
Domain decomposition. For certain cost functions, the domain D D D can be partitioned into D 1 D_1 D 1 and D 2 D_2 D 2 , allowing the problem to be reduced to separate instances over these two domains. To make this work, one must ensure that every list is contained entirely in either D 1 D_1 D 1 or D 2 D_2 D 2 and that variables with lists contained in different parts do not interact.
These algorithmic ideas must naturally be reflected in the proof of Theorem 1.1. Although they provide useful clues, their counterparts in the general setting take substantially different forms:
Polynomial-time solvability. The dichotomy theorem of Thapper and Živný [79 ] shows that the polynomial-time solvable cases of finite-valued VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) can be solved using a linear programming relaxation. For our result with hard lists, we use a reduction to submodular function minimization from the work of Cohen, Cooper, and Jeavons [CCJ08], as was done in [57 ] .
Noninteraction instead of incomparability. Although incomparability (that is, no value dominates another) is a natural notion, it is not the right one in the general setting. For example, when all soft lists are available, any two distinct values are incomparable by definition. However, if two values play identical roles in every constraint of arity at least two and differ only in unary
constraints, there is no need to retain both in the list of a variable. We therefore define the more general notion of noninteraction , which turns out to be useful both for algorithmic preprocessing and for lower bounds.
Overlapping decompositions. Rather than partitioning the domain into disjoint parts, we introduce decompositions of a different type. Roughly speaking, depending on Γ \Gamma Γ there is a finite number of blocks , which guide the decomposition process. The variables of the instance can then be assigned to these blocks, and our preprocessing ensures that only variables within the same block can be neighbors in the primal graph. This way, we decompose the input instance into a number of output instances that can be optimized separately. Interestingly, this is not a domain decomposition in the sense that variables assigned to different blocks can have the same domain value in their available sets (that is, not forbidden by hard-list constraints).
Local instance-specific preprocessing. As noted above, if a a a is at least as good as b b b in every finite-valued constraint of Γ \Gamma Γ , then b b b can be discarded whenever both values occur in the list of a variable. However, this dominance need not hold globally across all constraints in Γ \Gamma Γ . It may instead hold only for a particular variable v v v in a particular instance: regardless of the values assigned to other variables, assigning a a a to v v v is always at least as good as assigning b b b . In this case, we can remove b b b from the list of v v v . At the same time, the reverse may hold for another variable v ′ v' v ′ , allowing us to remove a a a from its list. More generally, the alternative to b b b may depend on the assignment to the neighbors of v v v . We use an LP-based technique to certify that values can be eliminated locally in this way. Related local preprocessing techniques restricting domain elements using LP have been studied in dead-end elimination (introduced in [27 ] ) [44 , 62 ] , for VCSPs with unary and binary cost functions [56 ] , and in the framework of relaxed improving mappings [75 ] . While earlier work used this type of preprocessing mainly as a heuristic way to improve running time, in our result this preprocessing provably improves the worst-case running time for certain constraint languages.
An interesting outcome of our study is that in the case of finite-valued soft-list languages, many of these ideas are unnecessary. It is sufficient to consider a pairwise interacting set of values at each variable, and the maximum size of such a set is the optimal base for the NP-hard cases. Therefore, no decomposition idea is relevant for the optimal algorithm and the local preprocessing is not needed.
Article structure. We give a technical overview of the work in § 2 . § 3 contains preliminaries, and § 4 contains central definitions and proofs necessary for both soft-list and hard-list languages. The results for soft-list and hard-list languages are proven in § 5 and § 6 , respectively.
AI usage. Our main result has been obtained from several conversations with AI tools, and we also used such tools for the purpose of writing and literature search, see § 8 for more details.
Technical Overview
In this section, we introduce the definitions necessary to discuss the technical results and sketch the main proofs.
A common theme in CSP dichotomy results is that, instead of considering Γ \Gamma Γ , it is more important to consider the set of all constraints that can be simulated using Γ \Gamma Γ : this closure of Γ \Gamma Γ is a mathematically important object, which can be studied, for example, from the perspective of universal algebra. While our proof does not use universal algebra explicitly, we often need to consider cost functions that are not in Γ \Gamma Γ , but can be expressed as a gadget using constraints from Γ \Gamma Γ . We write pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) for the expressive power [11 , 79 ] of Γ \Gamma Γ : cost functions obtained from finite weighted sums of constraints from Γ \Gamma Γ by minimizing over auxiliary variables, allowing an additive rational shift provided that the resulting cost function is nonnegative. It is easy to see that for any finite Δ ⊆ pow ( Γ ) \Delta\subseteq\operatorname{pow}(\Gamma) Δ ⊆ pow ( Γ ) , an instance of VCSP ( Γ ∪ Δ ) \operatorname{VCSP}(\Gamma\cup\Delta) VCSP ( Γ ∪ Δ ) can be reduced to an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) by replacing each constraint using a Δ \Delta Δ by a constant-sized gadget that uses only cost functions from Γ \Gamma Γ . Moreover, this reduction increases treewidth only by at most a constant depending on Δ \Delta Δ . This means that in the lower-bound proof, we are essentially free to use constraints also from pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Soft-List Languages
For soft-list languages, the optimum running time can be stated in a relatively simple way: after retaining one representative of each additive-equivalence class (defined below), an NP-hard problem is “as hard as possible”: standard dynamic programming on the reduced domain has the optimal exponential base. In this subsection, we formally state this result and sketch its proof, which introduces some important concepts in the study of VCSP(Γ \Gamma Γ ). In Section 2.2, we extend the discussion to the hard-list case, where the lack of all unary cost functions makes further nontrivial preprocessing and decomposition techniques relevant.
Additive equivalence. Let us focus first on the case where Γ \Gamma Γ is a finite-valued soft-list language. The first observation is that in this case any two distinct elements are incomparable: for every pair of distinct elements a , b ∈ D a,b \in D a , b ∈ D , the language Γ \Gamma Γ contains a unary constraint where a a a is strictly better than b b b , as well as a unary constraint where b b b is strictly better than a a a . At first, this suggests that we cannot obtain any significant improvement by restricting to an incomparable set of values. However, we can still get some improvement if we look at the unary constraints and the constraints of higher arity separately. Suppose that there are two values a , b ∈ D a,b \in D a , b ∈ D that play exactly the same role in every cost function f ∈ Γ f \in\Gamma f ∈ Γ of arity at least 2. Then, at every variable v v v , it is sufficient to consider as a candidate value only one of a a a and b b b : the one that has lower cost in the unary constraints on v v v .
Playing exactly the same role in every cost function f ∈ Γ f \in\Gamma f ∈ Γ of arity at least 2 is an equivalence relation, and this observation implies that the maximum number of values we need to consider at a variable is the number of these equivalence classes. However, the situation is more complicated than that. Consider the following example, where the soft-list family Γ \Gamma Γ over D = { 1 , 2 , 3 } D = \{1,2,3\} D = { 1 , 2 , 3 } consists of the following two functions and the soft lists:
f 1 ( x , y ) = { 1 if x = 1 or x = y = 3 , 0 otherwise, f 2 ( x , y ) = { 1 if x = 2 or x = y = 3 , 0 otherwise. f_1(x,y) =
\begin{cases}
1 & \text{if } x=1 \text{ or } x=y=3,\\
0 & \text{otherwise,}
\end{cases}
\qquad
f_2(x,y) =
\begin{cases}
1 & \text{if } x=2 \text{ or } x=y=3,\\
0 & \text{otherwise.}
\end{cases} f 1 ( x , y ) = { 1 0 if x = 1 or x = y = 3 , otherwise, f 2 ( x , y ) = { 1 0 if x = 2 or x = y = 3 , otherwise.
Clearly, no two values of D D D play the same role in these binary functions, partitioning D D D into three singleton equivalence classes. However, if we define g ( x , y ) g(x,y) g ( x , y ) to be 1 if x = y = 3 x=y=3 x = y = 3 and 0 otherwise, then f i ( x , y ) f_i(x,y) f i ( x , y ) can be expressed as g ( x , y ) g(x,y) g ( x , y ) plus a unary function that is 1 if x = i x=i x = i and 0 otherwise. Thus every instance of VCSP(Γ \Gamma Γ ) can be rewritten with constraints involving g g g and unary constraints. As 1 and 2 play the same role in the function g g g , this means that we have only two equivalence classes: { 1 , 2 } \{1,2\} { 1 , 2 } and { 3 } \{3\} { 3 } .
This example suggests that we should consider two values equivalent if they can be made equivalent in every cost function by adding unary constraints. We formalize this in the following definition: we say that a , b ∈ D a,b \in D a , b ∈ D are additively equivalent in Γ \Gamma Γ if for every f ∈ Γ f \in\Gamma f ∈ Γ of arity r r r and every i ∈ [ r ] i \in[r] i ∈ [ r ] , there is a constant c f , i a , b c_{f,i}^{a,b} c f , i a , b such that if an r r r -tuple has value b b b at position i i i , changing that value to a a a adds c f , i a , b c_{f,i}^{a,b} c f , i a , b to its f f f -value, independently of the other entries. In the example above, we have c f 1 , 1 1 , 2 = 1 c_{f_1,1}^{1,2}=1 c f 1 , 1 1 , 2 = 1 and c f 2 , 1 1 , 2 = − 1 c_{f_2,1}^{1,2}=-1 c f 2 , 1 1 , 2 = − 1 . It is easy to show that additive equivalence is transitive and forms an equivalence relation ≡ Γ \equiv_\Gamma ≡ Γ . It follows that essentially we have to consider only one representative from each class, or, in other words, we can reduce the problem to an instance of VCSP(Γ ′ \Gamma' Γ ′ ) where the domain size is the number of ≡ Γ \equiv_\Gamma ≡ Γ classes in Γ \Gamma Γ . This results in an algorithm where the base of the exponent is the number of such equivalence classes. A similar use of equivalence classes underlies the backtracking algorithm of [46 ] for VCSP(Γ \Gamma Γ ) with unary and binary constraints. It turns out that in the case of soft-list languages, this algorithmic idea already gives optimal running time.
Theorem 2.1 (Follows from Theorems 5.4 and 5.8 and Lemmas 2.2 and 5.6 ). Let D D D be a fixed finite domain and Γ \Gamma Γ a finite-valued soft-list language over D D D . Let q Γ q_\Gamma q Γ be the number of equivalence classes of ≡ Γ \equiv_\Gamma ≡ Γ . Then, the following hold:
(1) There is an algorithm that, given a VCSP(Γ \Gamma Γ ) instance I I I together with a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , solves I I I in time
( q Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (q_\Gamma)^{\operatorname{tw}} \cdot(|I| + |\mathcal{T}|)^{O(1)}. ( q Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (2) If VCSP(Γ \Gamma Γ ) is NP-hard, then for every ε > 0 \varepsilon> 0 ε > 0 , no algorithm can solve the problem in time
( q Γ − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (q_\Gamma- \varepsilon)^{\operatorname{tw}} \cdot(|I| + |\mathcal{T}|)^{O(1)}, ( q Γ − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , when the input instance I I I is given together with a tree decomposition T \mathcal{T} T of width tw \operatorname{tw} tw of the primal graph of I I I , unless tw-SET H \textup{tw-SET}H tw-SET H is false.
The algorithmic result (1) follows essentially from the discussion above. For the lower bound (2), we show that the number q Γ q_{\Gamma} q Γ of equivalence classes is the same as c Γ c_{\Gamma} c Γ . Therefore, the same straightforward lower bound arguments as in the lower bound of Theorem 1.1 (expressing c Γ c_{\Gamma} c Γ -Coloring or Max Cut) can be used.
Lemma 2.2. Let D D D be a fixed finite domain, and Γ \Gamma Γ be a finite-valued soft-list language over D D D . If c Γ ≥ 2 c_{\Gamma} \ge2 c Γ ≥ 2 , then c Γ = q Γ c_{\Gamma} = q_{\Gamma} c Γ = q Γ .
It is easy to see that c Γ ≤ q Γ c_{\Gamma} \le q_{\Gamma} c Γ ≤ q Γ : if a a a and b b b are additively equivalent, then we cannot express a disequality on a a a and b b b . The difficult part of the proof is showing c Γ ≥ q Γ c_{\Gamma} \ge q_{\Gamma} c Γ ≥ q Γ : if we take one value from each equivalence class, then we can express a disequality on the set S S S of these values. In fact, we show a stronger statement: any finite cost function on S S S can be expressed. While this might seem like overkill for the lower bound (as discussed above, it is sufficient to express a disequality), a general proof for all functions is not significantly more complicated than a proof for a fixed function such as disequality. Moreover, in the hard-list case, we indeed need to express more complicated cost functions in an inductive step, and hence later in the overview we will refer back to this construction. For simplicity, we state the result here for the case when the elements of D D D are pairwise additively nonequivalent.
Lemma 2.3 (Follows from Theorem 5.8 and Lemma 5.9). Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued soft-list language over D D D whose domain elements are pairwise additively nonequivalent. If VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) is not polynomial-time solvable, then pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains every finite-valued cost function.
Interaction. To prove Lemma 2.3, we need to understand what it means for the values in a set to be pairwise additively nonequivalent. The lower-bound constructions crucially depend on the following definition, both for soft-list and hard-list languages. Because we are using this definition in the case of hard-list languages, we require that neither value in each of the two pairs dominates the other. For soft-list languages, this condition holds automatically, as the unary cost functions make the values pairwise incomparable. However, this extra condition will play a role for hard-list languages.
Definition 2.4 (Interacting pairs). Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . Distinct elements a , b ∈ D a,b \in D a , b ∈ D form an interacting pair if neither dominates the other and there are distinct elements c , d ∈ D c,d \in D c , d ∈ D , neither of which dominates the other, and a finite-valued binary cost function f ∈ pow ( Γ ) f \in\operatorname{pow}(\Gamma) f ∈ pow ( Γ ) such that
f ( a , c ) − f ( b , c ) ≠ f ( a , d ) − f ( b , d ) . f(a,c)-f(b,c) \ne f(a,d)-f(b,d). f ( a , c ) − f ( b , c ) = f ( a , d ) − f ( b , d ) . We say that { c , d } \{c,d\} { c , d } and f f f witness the interaction of a , b a,b a , b . A set is pairwise interacting if every pair of its distinct elements interacts. If two distinct elements do not interact, they form a noninteracting pair.
Intuitively, the inequality means that if we consider the function f ( x , y ) f(x,y) f ( x , y ) and look at the unary functions f c ( x ) f_c(x) f c ( x ) and f d ( x ) f_d(x) f d ( x ) obtained by substituting y = c y=c y = c and y = d y=d y = d , respectively, then these two unary functions restricted to { a , b } \{a,b\} { a , b } are really different and not just by a constant shift: replacing a a a with b b b changes the cost in different ways in the two unary functions. Note that the inequality is equivalent to f ( a , c ) − f ( a , d ) ≠ f ( b , c ) − f ( b , d ) f(a,c)-f(a,d) \ne f(b,c)-f(b,d) f ( a , c ) − f ( a , d ) = f ( b , c ) − f ( b , d ) , giving also the interpretation that substituting x = a x=a x = a and x = b x=b x = b leads to different unary functions. Therefore, in a sense, the function f f f can distinguish between a a a and b b b and can propagate the choice between them: depending on this choice at x x x , the resulting unary constraint on y y y changes. A very similar definition is used by Helaioui and Naanaa [46 ] in the context of modularity.
For soft-list languages, additive equivalence is exactly the same as not interacting. Assuming that the elements of D D D are pairwise not additively equivalent, we may assume that the elements of D D D are pairwise interacting.
Lemma 2.5 (Follows from Lemma 5.11). Let D D D be a finite domain and Γ \Gamma Γ be a finite-valued soft-list language over D D D . Then, two distinct elements d 1 , d 2 ∈ D d_1,d_2 \in D d 1 , d 2 ∈ D are additively equivalent if and only if they do not interact.
Moves. The definition of interaction means that the choice between a a a and b b b at variable x x x has some kind of effect on how c c c and d d d are valued at variable y y y . When transferring information in a lower-bound proof, we would like to make this effect more specific: ideally, we would like to say that x = a x=a x = a forces y = c y=c y = c , while x = b x=b x = b forces y = d y=d y = d . The following definition expresses the existence of such a binary function:
Definition 2.6 (Moves and reversing moves). Let D D D be a domain and Γ \Gamma Γ a constraint language over D D D . Let { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } be two subsets of D D D of size 2 each. A binary cost function g g g is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) if
g ( a , c ) = g ( b , d ) < g ( a , d ) = g ( b , c ) . g(a,c)=g(b,d)<g(a,d)=g(b,c). g ( a , c ) = g ( b , d ) < g ( a , d ) = g ( b , c ) . We call the move finite-valued if g ( x , y ) < ∞ g(x,y)<\infty g ( x , y ) < ∞ for all x , y ∈ D x,y\in D x , y ∈ D . If there is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) we write ( a , b ) ⇝ ( c , d ) (a,b)\rightsquigarrow(c,d) ( a , b ) ⇝ ( c , d ) . If there is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) or to ( d , c ) (d,c) ( d , c ) we write { a , b } ⇝ { c , d } \{a,b\}\rightsquigarrow\{c,d\} { a , b } ⇝ { c , d } .
A move from ( a , b ) (a,b) ( a , b ) to ( b , a ) (b,a) ( b , a ) is a reversing move on { a , b } \{a,b\} { a , b } ; equivalently, it satisfies
g ( a , b ) = g ( b , a ) < g ( a , a ) = g ( b , b ) . g(a,b)=g(b,a)<g(a,a)=g(b,b). g ( a , b ) = g ( b , a ) < g ( a , a ) = g ( b , b ) . We say that Γ \Gamma Γ expresses a reversing move on { a , b } \{a,b\} { a , b } if such a function belongs to pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Intuitively, an expressible reversing move on { a , b } \{a,b\} { a , b } is a function f ∈ pow ( Γ ) f\in\operatorname{pow}(\Gamma) f ∈ pow ( Γ ) that expresses the binary disequality function: f ( a , b ) = f ( b , a ) < f ( a , a ) = f ( b , b ) f(a,b)=f(b,a)<f(a,a)=f(b,b) f ( a , b ) = f ( b , a ) < f ( a , a ) = f ( b , b ) . The dichotomy result of Thapper and Živný [79 ] for soft-list VCSP( Γ ) (\Gamma) ( Γ ) implies that if VCSP( Γ ) (\Gamma) ( Γ ) is not polynomial-time solvable, then there are distinct a , b ∈ D a,b\in D a , b ∈ D such that there is a reversing move on { a , b } \{a,b\} { a , b } . Moreover, if there is such a reversing move, then in a fairly standard way we can express every finite-valued cost function over { a , b } \{a,b\} { a , b } .
To prove Lemma 2.3, we need to express finite-valued cost functions not only on { a , b } \{a,b\} { a , b } , but on the full domain. To make this possible, we need to “translate” other elements of D D D into a combination of values in { a , b } \{a,b\} { a , b } . The key combinatorial insight that makes this possible in the case of soft-list languages (but need not hold for hard-list languages) is that there is a move from any interacting pair to { a , b } \{a,b\} { a , b } .
Lemma 2.7. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D that expresses all soft lists. For any interacting pairs { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } , there is a finite-valued move { a , b } ⇝ { c , d } \{a,b\}\rightsquigarrow\{c,d\} { a , b } ⇝ { c , d } .
The proof of Lemma 2.7 turns out to be a relatively simple case analysis. The definition of interacting pairs means that there is a pair { a ′ , b ′ } \{a',b'\} { a ′ , b ′ } for { a , b } \{a,b\} { a , b } and a pair { c ′ , d ′ } \{c',d'\} { c ′ , d ′ } for { c , d } \{c,d\} { c , d } satisfying the conditions in Definition 2.4. Then we can consider different cases depending on, for example, whether { a , b } \{a,b\} { a , b } and { c ′ , d ′ } \{c',d'\} { c ′ , d ′ } satisfy Definition 2.4 to obtain a sequence of moves from { a , b } \{a,b\} { a , b } to { c , d } \{c,d\} { c , d } and use the fact that moves are transitive in the case of soft-list or hard-list languages.
Translation to a 2-element set. The proof of Lemma 2.3 is based on a translation principle used already by Esmer et al. [35 ] . As discussed above, the assumption that VCSP( Γ ) (\Gamma) ( Γ ) is not polynomial-time solvable implies that there is a reversing move on some { a , b } \{a,b\} { a , b } and pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains every finite-valued cost function on { a , b } \{a,b\} { a , b } . We construct a gadget as follows. Consider an “input” variable x x x and, for every { c , d } ⊆ D \{c,d\}\subseteq D { c , d } ⊆ D of size two, an “output” variable y { c , d } y_{\{c,d\}} y { c , d } . For every such { c , d } \{c,d\} { c , d } , let us introduce a constraint on x x x and y { c , d } y_{\{c,d\}} y { c , d } whose cost function is the move from { c , d } \{c,d\} { c , d } to { a , b } \{a,b\} { a , b } . Let us add unary cost functions on y { c , d } y_{\{c,d\}} y { c , d } such that any value other than a a a or b b b has prohibitively large cost. Consider now assigning a value c c c to x x x . It has some number of minimum-cost ways of extending it to the y y y variables; that is, for every c c c there is some number of vectors in { a , b } ( ∣ D ∣ 2 ) \{a,b\}^{\binom{|D|}{2}} { a , b } ( 2 ∣ D ∣ ) that result in minimum cost. The key observation is that for distinct c , d ∈ D c,d\in D c , d ∈ D , these vectors are distinct. Indeed, consider the variable y { c , d } y_{\{c,d\}} y { c , d } and recall that a constraint with a move from { c , d } \{c,d\} { c , d } to { a , b } \{a,b\} { a , b } was introduced on x x x and y { c , d } y_{\{c,d\}} y { c , d } . Therefore, the value of this variable in any vector corresponding to c c c should be different from the value of this variable in any vector corresponding to d d d . By introducing additional unary cost constraints on variable x x x , we can ensure that for any c ∈ D c\in D c ∈ D on x x x , the minimum-cost extension has the same cost. This means that we can express a cost function where in every minimum-cost assignment, the combination of a a a ’s and b b b ’s on the ( ∣ D ∣ 2 ) \binom{|D|}{2} ( 2 ∣ D ∣ ) variables y y y uniquely determines the value of variable x x x . This last step, introducing the normalizing unary cost constraints on x x x , may seem like a minor technical step. However, as we shall see, this step plays an important role in the difference between the soft-list case and the hard-list case, as in the latter case adding normalizing unary cost constraints may not always be possible.
To express a cost function f f f of arity r r r required by Lemma 2.3, we introduce r r r copies of this construction. This results in a cost function where in every minimum-cost assignment, the combination of a a a ’s and b b b ’s on the r ( ∣ D ∣ 2 ) r\binom{|D|}{2} r ( 2 ∣ D ∣ ) variables y y y uniquely determines the values of the r r r variables x x x . Now we can introduce a constraint of arity r ( ∣ D ∣ 2 ) r\binom{|D|}{2} r ( 2 ∣ D ∣ ) on all the y y y variables that gives a specific cost for each combination in { a , b } r ( ∣ D ∣ 2 ) \{a,b\}^{r\binom{|D|}{2}} { a , b } r ( 2 ∣ D ∣ ) . We set this cost depending on the assignment on the x x x variables forced by the value of the y y y variables, and on what cost f f f assigns to this combination in D r D^r D r . As we assumed that every finite-valued cost function on { a , b } \{a,b\} { a , b } is in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , this construction proves that f f f is also in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Figure 1 illustrates this construction for a domain of size four and a ternary cost function.
Figure 1. Translation construction for d = ∣ D ∣ = 4 d = \lvert D\rvert= 4 d = ∣ D ∣ = 4 and r = 3 r = 3 r = 3 , with D = { 1 , 2 , 3 , 4 } D = \{1,2,3,4\} D = { 1 , 2 , 3 , 4 } and a reversing pair { 1 , 2 } ⊆ D \{1,2\} \subseteq D { 1 , 2 } ⊆ D . Each input x i ∈ D x_i \in D x i ∈ D is connected to six outputs: the edge to y i , j k y_{i,jk} y i , j k represents a move from { j , k } \{j,k\} { j , k } to { 1 , 2 } \{1,2\} { 1 , 2 } . Unary penalties restrict each output to { 1 , 2 } \{1,2\} { 1 , 2 } (omitted from the drawing), and the unary cost u i u_i u i normalizes the minimum extension cost independently of x i x_i x i . Each minimizing output tuple y ˉ i \bar{y}_i y ˉ i determines x i x_i x i uniquely. After sufficiently weighting the move gadgets, the cost function g g g on the 3 ( 4 2 ) = 18 3\binom{4}{2} = 18 3 ( 2 4 ) = 18 outputs assigns the desired cost f ( x 1 , x 2 , x 3 ) f(x_1,x_2,x_3) f ( x 1 , x 2 , x 3 ) to the corresponding encodings and a sufficiently large cost to all other tuples. Minimizing over the outputs realizes f f f up to an additive constant.
Hard-List Languages
In the case of hard-list languages, each variable has a list L v L_v L v of available elements, which are the values not excluded by an infinite cost in a unary constraint. An easy observation is that the base of the exponent in the running time can be improved from the domain size to the (potentially much smaller) maximum list size: standard dynamic programming on a tree decomposition needs to consider only assignments that use an available element at each variable in a bag [40 , 56 , 77 ] . Therefore, our main algorithmic goal in this section is to argue that the maximum list size can be provably decreased for some hard-list languages.
Lemma 2.8. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite constraint language over D D D whose cost functions are finite-valued or hard lists. Given an instance I I I of VCSP(Γ \Gamma Γ ) with variable set V V V and a tree decomposition T T T of its primal graph of width tw \operatorname{tw} tw , set c = max { ∣ L v ∣ : v ∈ V } c = \max\{\lvert L_v\rvert: v \in V\} c = max {∣ L v ∣ : v ∈ V } . One can compute Opt ( I ) \operatorname{Opt}(I) Opt ( I ) and an optimal assignment in time c tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) c^{\operatorname{tw}} \cdot(\lvert I\rvert+ \lvert T\rvert)^{O(1)} c tw ⋅ (∣ I ∣ + ∣ T ∣ ) O ( 1 ) .
The fundamental difference between soft-list and hard-list languages is that in the latter case, Lemma 2.7 is no longer true: it may be the case that for some interacting pairs { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } , there is no finite-valued move from { a , b } \{a,b\} { a , b } to { c , d } \{c,d\} { c , d } . This allows us to identify possibly overlapping blocks of the domain that do not interact with each other, and to reduce the problem to separate instances over these blocks.
The move graph. As there may be no finite-valued move between certain interacting pairs, it is natural to define a graph that expresses which moves exist; this idea was also used in [35 ] . The move graph G Γ G_\Gamma G Γ (of Γ \Gamma Γ ) has a vertex ( a , b ) (a,b) ( a , b ) for each ordered pair a , b ∈ D a,b \in D a , b ∈ D such that { a , b } \{a,b\} { a , b } is an interacting pair. There is an edge between ( a , b ) (a,b) ( a , b ) and ( c , d ) (c,d) ( c , d ) if there is a finite-valued move ( a , b ) ⇝ ( c , d ) (a,b) \leadsto(c,d) ( a , b ) ⇝ ( c , d ) . A similar graph appeared in [76 , 57 , 31 ] .
In the case of soft-list languages, the move graph is complete (assuming the elements are pairwise additively nonequivalent and a reversing move exists). This is no longer true for hard-list languages, and in fact the move graph may have multiple connected components (see Example 2.9 ). A key insight in the hard-list case is that we can essentially treat each connected component of the move graph separately, and that the optimal base of the exponent is determined by the “hardest” component.
Example 2.9. Let D = { a , b , c , d } D = \{a,b,c,d\} D = { a , b , c , d } and let Γ \Gamma Γ consist of all hard lists and the symmetric binary cost function
Both a a a and b b b dominate d d d , while the four pairs { a , c } \{a,c\} { a , c } , { a , b } \{a,b\} { a , b } , { c , b } \{c,b\} { c , b } , and { c , d } \{c,d\} { c , d } are interacting, each witnessed by itself and f f f . The move graph (Definition 6.4) has exactly three connected components:
C 1 = { ( a , c ) , ( c , a ) , ( a , b ) , ( b , a ) , ( c , b ) , ( b , c ) } , C 2 = { ( c , d ) } , C 3 = { ( d , c ) } . \begin{aligned}
C_1 &= \{(a,c),(c,a),(a,b),(b,a),(c,b),(b,c)\},\\
C_2 &= \{(c,d)\}, \qquad C_3 = \{(d,c)\}.
\end{aligned} C 1 C 2 = {( a , c ) , ( c , a ) , ( a , b ) , ( b , a ) , ( c , b ) , ( b , c )} , = {( c , d )} , C 3 = {( d , c )} . Indeed, on S = { a , b , c } S = \{a,b,c\} S = { a , b , c } the function f f f has cost 2 on equal arguments and 1 on distinct arguments. It therefore gives reversing moves on every pair in S S S , and interaction between these pairs connects all six orderings in C 1 C_1 C 1 . On { c , d } \{c,d\} { c , d } , f f f gives a loop at each of ( c , d ) (c,d) ( c , d ) and ( d , c ) (d,c) ( d , c ) , but no expressible finite-valued move connects these two vertices. ♦
It is not difficult to observe that every component of the move graph is a clique: if ( a , b ) (a,b) ( a , b ) and ( c , d ) (c,d) ( c , d ) are in the same component, then there is a path of moves from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) , and by transitivity of moves, there is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) . Therefore, if a component contains both ( a , b ) (a,b) ( a , b ) and ( b , a ) (b,a) ( b , a ) (as in the case of C 1 C_1 C 1 ), then there is a reversing move on { a , b } \{a,b\} { a , b } , which will be needed to prove hardness using the values appearing in the component. We call such a component a reversing block , and we will focus on such blocks in the hardness proof. It can be observed that if ( a , b ) ⇝ ( c , d ) (a,b) \rightsquigarrow(c,d) ( a , b ) ⇝ ( c , d ) , then ( b , a ) ⇝ ( d , c ) (b,a) \rightsquigarrow(d,c) ( b , a ) ⇝ ( d , c ) . Therefore, if a component C C C does not contain a reversing move, then reversing every pair of C C C gives another component C ′ C' C ′ (see, e.g., the components C 2 C_2 C 2 and C 3 C_3 C 3 in the example above). In this case, we call the union of C C C and C ′ C' C ′ a nonreversing block .
An interacting pair { a , b } \{a,b\} { a , b } belongs to a block B B B if ( a , b ) ∈ B (a,b) \in B ( a , b ) ∈ B ; since blocks are closed under reversal, this is equivalent to ( b , a ) ∈ B (b,a) \in B ( b , a ) ∈ B . More generally, a pairwise interacting set S ⊆ D S \subseteq D S ⊆ D with ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 belongs to B B B if every pair of distinct elements of S S S belongs to B B B . The following important lemma shows that every pairwise interacting set of size at least two belongs to a unique block.
Lemma 2.10. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Let L ⊆ D L \subseteq D L ⊆ D be pairwise interacting and of size at least 2. All pairs of distinct elements of L L L belong to one block of G Γ G_\Gamma G Γ .
Preprocessing. The definitions of interaction and blocks of the move graph allow the following three preprocessing rules, which are used in the proof of Theorem 1.1 to reduce the instance to a simpler form.
Dominated values. If a value a a a dominates another value b b b , then b b b can be removed from the list of any variable where both a a a and b b b are available without changing the optimum value of the instance. Therefore, we can assume that no value is dominated by another value in the same list.
Noninteracting values. After removing dominated values, if two values a a a and b b b available at v v v do not interact, then it is sufficient to keep only one of them: the other one plays the same role in every constraint of arity at least two, up to an additive difference in the cost. Therefore, if we keep only the one with lower total cost after summing these additive differences over all incident constraints, we can ignore the other value without changing the optimum value of the instance. This means that we can assume that all values in the lists are pairwise interacting. In particular, it follows by Lemma 2.10 that, for any variable v v v with at least two available values, there is a block B v B_v B v of the move graph such that any pair of available values at v v v is in B v B_v B v .
Decomposing the instance. Let V B V_B V B be the set of variables v v v with B v = B B_v = B B v = B . We claim that we can separate the instance into subinstances on the variable sets V B V_B V B for each block B B B of the move graph. Suppose that there is a binary constraint f ( x , y ) f(x,y) f ( x , y ) with x ∈ V B x \in V_B x ∈ V B and y ∈ V B ′ y \in V_{B'} y ∈ V B ′ for distinct blocks B B B and B ′ B' B ′ . Suppose that a , b a,b a , b are available at x x x and c , d c,d c , d are available at y y y . Then { a , b } \{a,b\} { a , b } belongs to B B B and { c , d } \{c,d\} { c , d } belongs to B ′ B' B ′ , and by definition of the move graph, { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } do not interact. This means that the constraint f ( x , y ) f(x,y) f ( x , y ) can be expressed as a sum of unary constraints on x x x and y y y , and therefore can be replaced by these unary constraints without changing the optimum value. The argument can be extended to higher-arity constraints.
Suppose that these preprocessing steps create a subinstance where every nonsingleton available set belongs to the same block B B B ; let k B k_B k B be the maximum size of an available set in this subinstance. If this block B B B is nonreversing, then earlier work implies that this subinstance can be solved in polynomial time [CCJ08, KŽ13, TŽ16]. Otherwise, we can solve the subinstance using a standard dynamic programming approach in time ( k B ) t w ⋅ n O ( 1 ) (k_B)^{\mathrm{tw}} \cdot n^{O(1)} ( k B ) tw ⋅ n O ( 1 ) : the maximum number of values that we need to consider at each variable is at most k B k_B k B .
By analogy to the soft-list case, it may be tempting to conjecture that this is the optimum approach: the best possible base of the exponent is the maximum size of a pairwise interacting set D B D_B D B belonging to any reversing block B B B of the move graph. However, if we try to follow the proof of the soft-list case but restricted to this block B B B , we run into a difficulty at the very end of the proof. It is true that there are a , b ∈ D B a,b \in D_B a , b ∈ D B such that there is a reversing move on { a , b } \{a,b\} { a , b } , and therefore every finite-valued cost function on { a , b } \{a,b\} { a , b } can be expressed. It is also true that for every two distinct elements c , d ∈ D B c,d \in D_B c , d ∈ D B there is a finite-valued move from { a , b } \{a,b\} { a , b } to { c , d } \{c,d\} { c , d } . The problem is that when we put these moves together to express an arbitrary cost function over D B D_B D B , we need to add unary cost functions on the x x x variables to normalize their cost. In our case, it may not be true that every finite-valued unary cost function on D B D_B D B is expressible.
Expressive sets. Hence, we consider subsets of values where all unary cost functions are available. For D ′ ⊆ D D' \subseteq D D ′ ⊆ D we say that Γ \Gamma Γ expresses all soft lists on D ′ D' D ′ if, for each B ⊆ D ′ B \subseteq D' B ⊆ D ′ there is a finite-valued unary function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c c c such that g ( d ) = c g(d) = c g ( d ) = c for d ∈ B d \in B d ∈ B , and g ( d ) = c + 1 g(d) = c + 1 g ( d ) = c + 1 for d ∈ D ′ ∖ B d \in D' \setminus B d ∈ D ′ ∖ B .
Definition 2.11 (Expressive set). Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . A set D ′ ⊆ D D' \subseteq D D ′ ⊆ D is expressive if
(1) D ′ D' D ′ is pairwise interacting, and
(2) Γ \Gamma Γ expresses all soft lists on D ′ D' D ′ .
With these definitions at hand, we can state our main results for hard lists in a different way. Concretely, we show that for all finite-valued hard-list languages, the constant c Γ c_\Gamma c Γ is equal to the maximum size of an expressive set D B ⊆ D D_B \subseteq D D B ⊆ D that belongs to a reversing block B B B , and one if there is no such set D B D_B D B .
Lemma 2.12. Let D D D be a finite domain, and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Then c Γ c_\Gamma c Γ is equal to
max ( { 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ } ) . \max\left(\{1\} \cup\{|S| \mid S \subseteq D \text{ is expressive and belongs to a reversing block of } G_\Gamma\}\right). max ( { 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ } ) .
In Lemma 2.12, the upper bound on c Γ c_\Gamma c Γ follows easily: if disequality is defined on a set S ⊆ D S \subseteq D S ⊆ D with ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 , then S S S is expressive and belongs to a reversing block of the move graph. For the lower bound, we can follow the same arguments as in Lemma 2.3 for soft-list languages: if we assume that S S S is an expressive set, then the availability of the finite-valued unary cost functions makes the proof go through.
We can prove the upper bound of Theorem 1.1(1) by ensuring that every available set L v L_v L v is expressive and belongs to a reversing block. Then by Lemma 2.12, the size of the largest available set is at most c Γ c_\Gamma c Γ , and we can apply Lemma 2.8 to solve the instance in time ( c Γ ) t w ⋅ n O ( 1 ) (c_\Gamma)^{\mathrm{tw}} \cdot n^{O(1)} ( c Γ ) tw ⋅ n O ( 1 ) . Thus the rest of the overview is devoted to presenting the preprocessing techniques that ensure that every available set is expressive and belongs to a reversing block.
Locally necessary values. Consider an instance I I I of VCSP( Γ ) (\Gamma) ( Γ ) . We say that a value a ∈ L v a \in L_v a ∈ L v is locally necessary at variable v v v if there is a partial assignment of the variables V ∖ { v } V \setminus\{v\} V ∖ { v } respecting their available sets such that a a a is the unique best extension of this assignment to a full assignment of I I I . If a a a is not locally necessary at v v v , then we can exclude it from the available set of v v v without changing the optimum cost: by definition, no matter what the values of the other variables in an optimum assignment are, there is a value other than a a a that can optimally extend this partial assignment to v v v .
Example 2.13. Let D = { a , b , c } D = \{a,b,c\} D = { a , b , c } and let Γ \Gamma Γ consist of all hard lists and the symmetric binary cost function
Table 2.
No two domain elements dominate one another, and each pair { x , y } \{x,y\} { x , y } witnesses its own interaction, since f ( x , x ) + f ( y , y ) ≠ 2 f ( x , y ) f(x,x)+f(y,y) \ne2f(x,y) f ( x , x ) + f ( y , y ) = 2 f ( x , y ) . Thus D D D is pairwise interacting, and all pairs belong to one block by Lemma 2.10. This block is reversing: pinning auxiliary variables to c c c expresses
g ( x , y ) = f ( x , y ) + 2 f ( x , c ) + 2 f ( y , c ) , g(x,y)=f(x,y)+2f(x,c)+2f(y,c), g ( x , y ) = f ( x , y ) + 2 f ( x , c ) + 2 f ( y , c ) ,
for which g ( a , b ) = g ( b , a ) = 7 < 8 = g ( a , a ) = g ( b , b ) g(a,b)=g(b,a)=7<8=g(a,a)=g(b,b) g ( a , b ) = g ( b , a ) = 7 < 8 = g ( a , a ) = g ( b , b ) .
Nevertheless, in any instance over Γ \Gamma Γ , the value b b b is not locally necessary at a variable whose available set is D D D . Indeed, for every z ∈ D z\in D z ∈ D ,
2 f ( b , z ) ≥ f ( a , z ) + f ( c , z ) . 2f(b,z)\ge f(a,z)+f(c,z). 2 f ( b , z ) ≥ f ( a , z ) + f ( c , z ) .
By symmetry, the same inequality holds when the variable occurs in the second position; a constraint using the variable in both positions also satisfies 2 f ( b , b ) ≥ f ( a , a ) + f ( c , c ) 2f(b,b)\ge f(a,a)+f(c,c) 2 f ( b , b ) ≥ f ( a , a ) + f ( c , c ) . Fix any available assignment to the other variables, and let C x C_x C x be its total cost when the variable in question receives x x x . Summing these inequalities with the constraint weights gives
2 C b ≥ C a + C c , and hence min { C a , C c } ≤ C b . 2C_b\ge C_a+C_c,\qquad\text{and hence}\qquad\min\{C_a,C_c\}\le C_b. 2 C b ≥ C a + C c , and hence min { C a , C c } ≤ C b .
Thus b b b can always be replaced by a a a or c c c , even though neither value dominates b b b and all pairs lie in a single reversing block. ♦
We emphasize that this definition is a local property of a specific instance and not something that can be deduced from Γ \Gamma Γ itself. For example, it is possible that an instance contains two variables x x x and y y y , such that a a a and b b b are both available at x x x and y y y , value a a a is not locally necessary at y y y , while b b b is not locally necessary at x x x .
Example 2.14. Let f f f be the function from Example 2.13, and let h h h be obtained by interchanging a a a and b b b in both arguments:
Table 3.
Let Γ \Gamma Γ consist of f f f , h h h , and all hard lists. The domain is still pairwise interacting and the move graph still has one reversing block, since the witnesses using f f f remain available. Consider the instance on three variables x , z , y x,z,y x , z , y , each with available set D = { a , b , c } D=\{a,b,c\} D = { a , b , c } , whose total cost is
f ( x , z ) + h ( z , y ) . f(x,z)+h(z,y). f ( x , z ) + h ( z , y ) .
At x x x , the value b b b is not locally necessary, by the inequality in the preceding example. However, a a a and c c c are locally necessary at x x x : they are uniquely cheapest when z = a z=a z = a and z = c z=c z = c , respectively. At y y y , the roles of a a a and b b b are interchanged: a a a is not locally necessary, whereas b b b and c c c are uniquely cheapest when z = b z=b z = b and z = c z=c z = c , respectively. Thus the only unnecessary value at x x x is b b b , while the only unnecessary value at y y y is a a a ; neither value is locally unnecessary at all variables of the instance. In fact, all three values are locally necessary at z z z , witnessed by ( x , y ) = ( b , b ) (x,y)=(b,b) ( x , y ) = ( b , b ) , ( a , a ) (a,a) ( a , a ) , and ( c , c ) (c,c) ( c , c ) for z = a , b , c z=a,b,c z = a , b , c , respectively. ♦
The significance of locally necessary values comes from the following crucial result. We show that if I I I is an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , B B B is a reversing block, and every available set contains only pairwise interacting values belonging to B B B (or has size one), and every available value is locally necessary, then every available set is expressive. Together with the fact that there is a reversing move on some a , b a,b a , b belonging to B B B and there is a move from any { c , d } \{c,d\} { c , d } to { a , b } \{a,b\} { a , b } , it further follows that pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains every finite-valued cost function on each available set.
Theorem 2.15 (Follows from Theorem 6.18 and Observation 6.16). Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D , and B B B a reversing block of G Γ G_\Gamma G Γ . Let I I I be an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) such that the available set L v L_v L v of each variable v v v :
belongs to B B B or has size one,
is pairwise interacting, and
has the property that each element of L v L_v L v is locally necessary at v v v .
Then, every available set of I I I is expressive.
This statement can be proved in an inductive way. The induction considers all nonempty subsets of the available sets; restricting a variable to a subset preserves local necessity for its remaining values. Consider a k k k -element available set L v = { a 1 , … , a k } L_v = \{a_1, \ldots, a_k\} L v = { a 1 , … , a k } . As every a i a_i a i is locally necessary, there is a partial assignment π i \pi_i π i on the remaining variables such that assigning a i a_i a i to v v v is the unique minimum-cost extension of π i \pi_i π i to the full instance I I I . To express any unary cost function on L v L_v L v , it is sufficient to express, for every i i i , a unary cost function f i f_i f i such that f i ( a i ) > f i ( a j ) f_i(a_i) > f_i(a_j) f i ( a i ) > f i ( a j ) for any j ≠ i j \ne i j = i , and f i ( a j ) = f i ( a j ′ ) f_i(a_j) = f_i(a_{j'}) f i ( a j ) = f i ( a j ′ ) for any j , j ′ ≠ i j, j' \ne i j , j ′ = i : nonnegative linear combinations of such f i f_i f i 's (with an additive shift) can express any unary function.
We obtain such an f i f_i f i as follows. Consider the cost function g g g on the variables V ∖ { v } V \setminus\{v\} V ∖ { v } which has some finite cost if the assignment on V ∖ { v } V \setminus\{v\} V ∖ { v } is the same as some π i ′ \pi_{i'} π i ′ for i ≠ i ′ i \ne i' i = i ′ , and a prohibitively large cost otherwise. If we can add a constraint to the instance with such a cost function g g g , then this expresses a unary constraint on v v v . This unary constraint has the property that a i a_i a i has strictly larger cost than a i ′ a_{i'} a i ′ for any i ≠ i ′ i \ne i' i = i ′ : no matter which of the k − 1 k - 1 k − 1 reasonable assignments π i ′ \pi_{i'} π i ′ is selected on V ∖ { v } V \setminus\{v\} V ∖ { v } , assigning a i ′ a_{i'} a i ′ to v v v is strictly better than assigning a i a_i a i . Furthermore, by modifying the value of g g g when the assignment is equal to π i ′ \pi_{i'} π i ′ , it is not difficult to ensure that the resulting unary cost function on v v v has the same value on a i ′ a_{i'} a i ′ for every i ≠ i ′ i \ne i' i = i ′ , and it is strictly larger on a i a_i a i .
Therefore, expressing all finite-valued unary cost functions on { a 1 , … , a k } \{a_1, \ldots, a_k\} { a 1 , … , a k } boils down to expressing such a cost function g g g . This seems to be a much harder task, as it is a cost function with high arity. However, we have made progress in an important sense. The cost g g g needs to be low only on k − 1 k - 1 k − 1 different assignments; in particular, for every variable v ′ ∈ V ∖ { v } v' \in V \setminus\{v\} v ′ ∈ V ∖ { v } , there is a list L v ′ ′ L'_{v'} L v ′ ′ of size at most k − 1 k - 1 k − 1 such that we can introduce a hard list restricting the domain of v ′ v' v ′ to L v ′ ′ L'_{v'} L v ′ ′ . By induction, we may assume that we can express every finite-valued unary cost function on every L v ′ ′ L'_{v'} L v ′ ′ . Therefore, using the fact that every nonsingleton L v ′ ′ L'_{v'} L v ′ ′ belongs to the reversing block B B B and using arguments as in the soft-list case, we can show that we can express the cost function g g g . That is, expressing unary cost functions on a k k k -element set reduces to being able to express unary cost functions on every set of at most k − 1 k - 1 k − 1 elements. For k = 2 k = 2 k = 2 , we can prove this directly using the definition of reversing blocks, establishing the base case of the induction.
Locally fractionally necessary values. This discussion suggests the following algorithm: after solving the nonreversing-block subinstances in polynomial time, let us repeatedly remove any value that is not locally necessary in the remaining subinstances, and then solve the problem using the standard dynamic programming approach. As every value is locally necessary, every available set is expressive, hence its size is not larger than c Γ c_\Gamma c Γ (recall Lemma 2.12 ) resulting in the required running time. However, it is not clear how to efficiently check if a value a a a is locally necessary at variable v v v : testing all possible partial assignments as in the definition is clearly not feasible. In fact, this is an NP-hard problem in general.
Instead of exactly determining if a value is locally necessary, we test for a weaker condition. Testing whether a a a is locally necessary at v v v can be formulated as testing whether the optimum of a mixed integer linear program is positive (see Mixed integer linear program 6.13). We say that a a a is locally fractionally necessary at v v v if the optimum of the LP relaxation of this mixed integer linear program is positive. This definition requires solving a linear program, so the condition can be tested in polynomial time. Clearly, local necessity implies local fractional necessity. Therefore, we can safely remove values from the available set if they are not even locally fractionally necessary, giving us a new polynomial-time preprocessing step. The test is repeated after each deletion until no further value can be removed (Lemma 6.17 ).
With this preprocessing, we achieve the weaker property that every value in every available set is locally fractionally necessary. However, the proof that every available set is expressive can be made to work under this weaker condition: Theorem 2.15 remains true even if we weaken locally necessary to locally fractionally necessary (see Theorem 6.18 ). Intuitively, a fractional solution of the LP gives an assignment that does not give a single value to each variable of V ∖ { v } V \setminus\{v\} V ∖ { v } , but instead assigns distributions over tuples to the incident constraints. Using that the fractional solution is rational, we can duplicate variables and constraints appropriately to obtain an instance I ′ I' I ′ and an assignment showing that the value is locally necessary at v v v in I ′ I' I ′ . We can use such blown-up instances in the proof showing that every finite-valued unary cost function on the available set is expressible.
Therefore, it is sufficient to ensure that every value in every available set is locally fractionally necessary. Every available set is then expressive, and hence has size at most c Γ c_\Gamma c Γ . Therefore, after this preprocessing, the standard dynamic programming approach proves the algorithmic part of Theorem 1.1.
Preliminaries
VCSPs. A VCSP is the natural optimization variant of a CSP [13 ] . A cost function is a function f : D a → Q ≥ 0 ∪ { ∞ } f:D^{a}\to\mathbb{Q}_{\ge0}\cup\{\infty\} f : D a → Q ≥ 0 ∪ { ∞ } , where a ≥ 0 a\ge0 a ≥ 0 is the arity of f f f , also denoted by arity ( f ) \operatorname{arity}(f) arity ( f ) . For an integer n ≥ 0 n\ge0 n ≥ 0 , write [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } , so [ 0 ] = ∅ [0]=\varnothing [ 0 ] = ∅ . For a fixed finite domain D D D and a finite set of cost functions Γ \Gamma Γ , an instance I = ( V , C , t ) I=(V,\mathcal{C},t) I = ( V , C , t ) of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) consists of a finite set of variables V V V , a finite family of constraints C \mathcal{C} C , and a cost target t ∈ Q t\in\mathbb{Q} t ∈ Q . Each constraint C ∈ C C\in\mathcal{C} C ∈ C is a triple ( f , S , w ) (f,S,w) ( f , S , w ) , where f ∈ Γ f\in\Gamma f ∈ Γ is a cost function denoted by cost f ( C ) \operatorname{cost}_{f}(C) cost f ( C ) , S ∈ V arity ( f ) S\in V^{\operatorname{arity}(f)} S ∈ V arity ( f ) is a tuple of arity ( f ) \operatorname{arity}(f) arity ( f ) variables called the scope of C C C , denoted by scope ( C ) \operatorname{scope}(C) scope ( C ) , and w ∈ Q > 0 w\in\mathbb{Q}_{>0} w ∈ Q > 0 is a positive rational weight, denoted by weight ( C ) \operatorname{weight}(C) weight ( C ) . For a variable assignment π : V → D \pi:V\to D π : V → D , write cost I ( π ) = ∑ C ∈ C weight ( C ) cost f ( C ) ( π ( scope ( C ) ) ) \operatorname{cost}_{I}(\pi)=\sum_{C\in\mathcal{C}}\operatorname{weight}(C)\operatorname{cost}_{f(C)}(\pi(\operatorname{scope}(C))) cost I ( π ) = ∑ C ∈ C weight ( C ) cost f ( C ) ( π ( scope ( C ))) , where π \pi π acts componentwise on tuples. The optimum cost is Opt ( I ) = min π : V → D cost I ( π ) \operatorname{Opt}(I)=\min_{\pi:V\to D}\operatorname{cost}_{I}(\pi) Opt ( I ) = min π : V → D cost I ( π ) , taking the value ∞ \infty ∞ if no finite-cost assignment exists. We also use cost \operatorname{cost} cost and Opt \operatorname{Opt} Opt for a weighted constraint system ( V , C ) (V,\mathcal{C}) ( V , C ) without a target, using the same formulas. The decision problem asks whether Opt ( I ) ≤ t \operatorname{Opt}(I)\le t Opt ( I ) ≤ t . We write ∣ I ∣ |I| ∣ I ∣ for the bit length of the encoding of I I I . The primal graph of an instance has vertex set V V V and connects two distinct vertices with an edge if they appear together in a constraint scope. Since all costs are nonnegative, every instance with a negative target is a no-instance. Throughout the paper, we shall assume all domains are nonempty and finite.
Remark 3.1. Requiring positive rational weights for the constraints is equivalent to requiring positive integer weights. Indeed, multiplying all weights and the target by a common denominator of the weights yields an equivalent instance. We allow rational weights for convenience, as they simplify the proofs. Similarly, the assumption that the costs are nonnegative is without loss of generality; if negative costs are involved they can be cleared by appropriate shifting.
A cost function is finite-valued if it never takes the value ∞ \infty ∞ . A constraint language Γ \Gamma Γ is finite-valued if all its cost functions are finite-valued. For a cost function f : D r → Q ≥ 0 ∪ { ∞ } f:D^{r}\to\mathbb{Q}_{\ge0}\cup\{\infty\} f : D r → Q ≥ 0 ∪ { ∞ } we define max f = max x ˉ ∈ D r f ( x ˉ ) \max f=\max_{\bar{x}\in D^{r}}f(\bar{x}) max f = max x ˉ ∈ D r f ( x ˉ ) , similarly for min f \min f min f .
We write pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) for the expressive power [11 , 79 ] of Γ \Gamma Γ : cost functions obtained from finite weighted sums of constraints from Γ \Gamma Γ by minimizing over auxiliary variables, allowing an additive rational shift provided that the resulting cost function is nonnegative. Hence, for each g ∈ pow ( Γ ) g\in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) of arity d d d there exists some gadget with distinguished “input” variables x 1 , … , x d x_{1},\ldots,x_{d} x 1 , … , x d , and auxiliary variables over which the cost is optimized, such that for any assignment y ˉ \bar{y} y ˉ to x 1 , … , x d x_{1},\ldots,x_{d} x 1 , … , x d the corresponding cost is g ( y ˉ ) g(\bar{y}) g ( y ˉ ) , up to an additive constant. The following simple lemma allows us to use a fixed finite family of expressed cost functions in reductions.
Lemma 3.2. Let D D D be a fixed finite domain, Γ \Gamma Γ a fixed constraint language over D D D , and Δ ⊆ pow ( Γ ) \Delta\subseteq\operatorname{pow}(\Gamma) Δ ⊆ pow ( Γ ) a fixed finite set of cost functions. There is a polynomial-time algorithm that, given an instance I I I of VCSP ( Γ ∪ Δ ) \operatorname{VCSP}(\Gamma\cup\Delta) VCSP ( Γ ∪ Δ ) and a path or tree decomposition of its primal graph of width k k k , constructs an equivalent instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) together with a decomposition of the same type and width at most k + O ( 1 ) k+O(1) k + O ( 1 ) . The constant in the width bound depends only on $\Delta.
Proof. The statement is trivial if Δ = ∅ \Delta=\varnothing Δ = ∅ , so we assume Δ \Delta Δ is nonempty. For each f ∈ Δ f\in\Delta f ∈ Δ , fix a gadget over Γ \Gamma Γ with cost F f ( x ˉ , y ˉ ) F_{f}(\bar{x},\bar{y}) F f ( x ˉ , y ˉ ) and a rational constant c f c_{f} c f such that
f ( x ˉ ) = min y ˉ F f ( x ˉ , y ˉ ) + c f , f(\bar{x})=\min_{\bar{y}}F_{f}(\bar{x},\bar{y})+c_{f}, f ( x ˉ ) = y ˉ min F f ( x ˉ , y ˉ ) + c f ,
where x ˉ \bar{x} x ˉ are its input variables and y ˉ \bar{y} y ˉ are its auxiliary variables. Replace every constraint ( f , S , w ) (f,S,w) ( f , S , w ) with f ∈ Δ f\in\Delta f ∈ Δ by a separate copy of this gadget, identifying its inputs with S S S , using fresh auxiliary variables, and multiplying every gadget weight by w w w . Keep all other constraints and set the new target to
t ′ = t − ∑ ( f , S , w ) ∈ C , f ∈ Δ w c f , t'=t-\sum_{\substack{(f,S,w)\in\mathcal{C},\\ f\in\Delta}}wc_{f}, t ′ = t − ( f , S , w ) ∈ C , f ∈ Δ ∑ w c f ,
where C \mathcal{C} C is the constraint family of I I I and t t t its target. For every assignment to the original variables, the separate auxiliary variables can be minimized independently. The minimum resulting cost is the original cost minus the same sum of weighted constants. This shows that the two instances are equivalent.
Let K K K be the largest number of auxiliary variables in one of the fixed gadgets. For each replaced constraint, its distinct variables form a clique in the original primal graph, so choose a bag containing the constraint scope. For a nullary constraint, use any bag (creating an empty bag if needed).
In a path decomposition, insert a copy of the chosen bag immediately after it and add all auxiliary variables of the gadget added for the constraint to the copy. Use a separate bag copy for each gadget. This preserves the property that each original variable appears in the bags of a connected subpath of the path decomposition, and every auxiliary variable appears in just its gadget’s bag.
In a tree decomposition, attach a new leaf bag containing the gadget’s inputs and auxiliary variables to the chosen bag. The bags containing each original variable remain connected, and each auxiliary variable appears only in its leaf. In both cases, the new bags cover all gadget constraints and have size at most k + 1 + K k+1+K k + 1 + K . Thus the width increases by at most the constant K K K .
Since Δ \Delta Δ is fixed and finite, every replaced constraint produces only constantly many constraints and auxiliary variables. Hence, the reduction takes polynomial time.
Lists. Next, we formally define the notions of hard and soft lists, and the notion of a finite-valued hard-list language.
Definition 3.3 (Hard lists). Let D D D be a finite domain. A hard list on D ′ ⊆ D D' \subseteq D D ′ ⊆ D is the cost function f f f defined by f ( d ) = 0 f(d)=0 f ( d ) = 0 if d ∈ D ′ d \in D' d ∈ D ′ and f ( d ) = ∞ f(d)=\infty f ( d ) = ∞ if d ∉ D ′ d \notin D' d ∈ / D ′ . A constraint language Γ \Gamma Γ over D D D contains all hard lists if, for all D ′ ⊆ D D' \subseteq D D ′ ⊆ D , the language Γ \Gamma Γ contains the hard list on D ′ D' D ′ .
Definition 3.4 (Finite-valued hard-list language). Let D D D be a finite domain and let H D \mathcal{H}_D H D be the set of all hard lists on D D D . A constraint language Γ \Gamma Γ over D D D is a finite-valued hard-list language if Γ = Φ ∪ H D \Gamma=\Phi\cup\mathcal{H}_D Γ = Φ ∪ H D for some finite-valued constraint language Φ \Phi Φ over D D D . Equivalently, Γ \Gamma Γ contains all hard lists and every cost function in Γ ∖ H D \Gamma\setminus\mathcal{H}_D Γ ∖ H D is finite-valued. In an instance over Γ \Gamma Γ , a non-hard-list constraint is a constraint whose cost function belongs to Γ ∖ H D \Gamma\setminus\mathcal{H}_D Γ ∖ H D .
Since hard lists can be seen as simply forbidding certain variable assignments, this leads to a natural notion of available elements.
Definition 3.5 (Available elements). Let D D D be a finite domain, let Γ \Gamma Γ be a constraint language over D D D whose cost functions are finite-valued or hard lists, and let I I I be an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) . The available set L v L_v L v of a variable v v v consists of those elements d ∈ D d \in D d ∈ D for which assigning d d d to v v v does not by itself make any constraint involving v v v incur infinite cost. Equivalently, L v L_v L v is the intersection of the sets allowed by the hard-list constraints imposed on v v v , with L v = D L_v=D L v = D if there are no such constraints. An element d d d is available at v v v if d ∈ L v d \in L_v d ∈ L v .
Next, we also formally define soft lists and soft-list languages.
Definition 3.6 (Soft lists and soft-list languages). Let B ⊆ D B \subseteq D B ⊆ D . The soft list on B B B is the unary cost function
h B ( d ) = { 0 , d ∈ B , 1 , d ∉ B . h_B(d)=
\begin{cases}
0, & d \in B,\\
1, & d \notin B.
\end{cases} h B ( d ) = { 0 , 1 , d ∈ B , d ∈ / B . We say that Γ \Gamma Γ expresses all soft lists if h B ∈ pow ( Γ ) h_B \in\operatorname{pow}(\Gamma) h B ∈ pow ( Γ ) for every B ⊆ D B \subseteq D B ⊆ D . If h B ∈ Γ h_B \in\Gamma h B ∈ Γ for every B ⊆ D B \subseteq D B ⊆ D , we say that Γ \Gamma Γ contains all soft lists.
For B ⊆ D B \subseteq D B ⊆ D , we say that Γ \Gamma Γ expresses all soft lists on B B B if, for every S ⊆ B S \subseteq B S ⊆ B , there is a finite-valued unary function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c \in\mathbb{Q} c ∈ Q such that g ( d ) = h S ( d ) + c g(d)=h_S(d)+c g ( d ) = h S ( d ) + c for every d ∈ B d \in B d ∈ B .
We call a finite constraint language Γ \Gamma Γ over D D D a soft-list language if, for every d ∈ D d \in D d ∈ D , Γ \Gamma Γ contains the unary cost function that takes value 1 1 1 at d d d and 0 0 0 at every other element of D D D .
Treewidth and pathwidth
For an introduction to treewidth and pathwidth, see, e.g., [16 Section 7] . For a supplied tree or path decomposition T \mathcal{T} T , we write ∣ T ∣ |\mathcal{T}| ∣ T ∣ for the bit length of its encoding, including its bags and underlying tree or path. We show lower bounds based on pw-SETH and tw-SETH, which we state formally below. The pw-SETH was introduced by Lampis [58 ] ; the tw-SETH was postulated in the work of Iwata and Yoshida [48 ] , and recently explored further by Lampis [60 ] .
Hypothesis 3.7 (pw-SETH). For all ε > 0 \varepsilon>0 ε > 0 there is no algorithm that can solve 3-SAT in time
( 2 − ε ) p w ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (2-\varepsilon)^{\mathrm{pw}} \cdot(|I|+|\mathcal{T}|)^{O(1)}, ( 2 − ε ) pw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , where the input consists of a 3-SAT instance I I I and a path decomposition T \mathcal{T} T of its primal graph of width pw.
Hypothesis 3.8 (tw-SETH). For all ε > 0 \varepsilon>0 ε > 0 there is no algorithm that can solve 3-SAT in time
( 2 − ε ) t w ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (2-\varepsilon)^{\mathrm{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)}, ( 2 − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , where the input consists of a 3-SAT instance I I I and a tree decomposition T \mathcal{T} T of its primal graph of width tw.
Lampis [58 ] showed that the pw-SETH is implied by the SETH (whose refutation is reported in recent preprints [69 , 21 ] ), the k k k -Orthogonal Vectors Assumption [81 ] , and the Set Cover Conjecture [15 ] . The tw-SETH is implied by the pw-SETH, and Lampis [60 ] showed that it is also implied by the k k k -Sum Hypothesis [1 ] and the k k k -Xor Hypothesis [34 ] . The traditional variants of the k k k -Sum and k k k -Xor hypotheses were recently proven false, because they are wrong when k = 3 k = 3 k = 3 [2 ] . A recent preprint [17 ] also disproves the k k k -Sum Hypothesis for all odd k k k . However, as explicitly discussed in [61 ] , the updated arXiv version of [60 ] , for the result of Lampis the following weaker variants suffice: for each k ≥ 3 k \ge3 k ≥ 3 the problem k k k -Sum, respectively k k k -Xor, cannot be solved in time O ( n k / 2 − ε ) O(n^{k/2-\varepsilon}) O ( n k /2 − ε ) , where n n n is the number of integers/vectors in each of the k k k given input lists, for any ε > 0 \varepsilon> 0 ε > 0 . These variants are, as of now, not refuted by these results. We use both the tw-SETH and pw-SETH because they offer different advantages: pw-SETH yields lower bounds in terms of pathwidth, whereas tw-SETH yields treewidth lower bounds under a weaker assumption. As discussed in § 1 , tw-SETH and pw-SETH are also implied by CNF-SETH, which has not been disproved in the recent results [69 , 21 ] .
Interaction and Moves
Before proving the results for finite-valued soft-list languages and finite-valued hard-list languages, we establish the expressibility results needed in both settings. First, we introduce the notion of a restriction to capture both soft and hard lists.
Definition 4.1 (Restrictions). Let B ⊆ D B \subseteq D B ⊆ D be nonempty. A restriction to B B B is a unary cost function h h h for which there is a constant c ∈ Q c \in\mathbb{Q} c ∈ Q such that h ( d ) = c h(d) = c h ( d ) = c for d ∈ B d \in B d ∈ B and h ( d ) > c h(d) > c h ( d ) > c for d ∉ B d \notin B d ∈ / B ; costs outside B B B can be infinite. We say that Γ \Gamma Γ expresses a restriction to B B B if such a function belongs to pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Observe that every soft or hard list on B B B is a restriction to B B B . Our results revolve around being able to express all cost functions on certain domain subsets, which we formally define next.
Definition 4.2 (Cost functions on a subset). Let B ⊆ D B \subseteq D B ⊆ D . We say that Γ \Gamma Γ expresses all finite-valued cost functions on B B B if, for every r ≥ 1 r \ge1 r ≥ 1 and every function f : B r → Q ≥ 0 f : B^r \to\mathbb{Q}_{\ge0} f : B r → Q ≥ 0 , there are a finite-valued cost function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c \in\mathbb{Q} c ∈ Q such that g ( d ˉ ) = f ( d ˉ ) + c g(\bar{d}) = f(\bar{d}) + c g ( d ˉ ) = f ( d ˉ ) + c for all d ˉ ∈ B r \bar{d} \in B^r d ˉ ∈ B r . If we require this only for r = 1 r = 1 r = 1 , we say that Γ \Gamma Γ expresses all finite-valued unary cost functions on B B B .
Expressing all finite-valued unary cost functions on B B B lets us prescribe costs within B B B , without any requirement on the costs outside B B B . Hence, it is quite different from restrictions, which restrict the optimum assignments and concern the entire domain. Next, we introduce the notion of a move, following the work of Esmer, Focke, Marx, and Rzążewski [35 ] and the idea, sometimes called a max-cut condition, from the work of Kolmogorov and Živný [57 ] , Huber, Krokhin, and Powell [45 ] , and Thapper and Živný [79 ] .
Definition 2.6 (Moves and reversing moves). Let D D D be a domain and Γ \Gamma Γ a constraint language over D D D . Let { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } be two subsets of D D D of size 2 each. A binary cost function g g g is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) if
g ( a , c ) = g ( b , d ) < g ( a , d ) = g ( b , c ) . g(a,c) = g(b,d) < g(a,d) = g(b,c). g ( a , c ) = g ( b , d ) < g ( a , d ) = g ( b , c ) . We call the move finite-valued if g ( x , y ) < ∞ g(x,y) < \infty g ( x , y ) < ∞ for all x , y ∈ D x,y \in D x , y ∈ D . If there is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) we write ( a , b ) ⇝ ( c , d ) (a,b) \leadsto(c,d) ( a , b ) ⇝ ( c , d ) . If there is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) or to ( d , c ) (d,c) ( d , c ) we write { a , b } ⇝ { c , d } \{a,b\} \leadsto\{c,d\} { a , b } ⇝ { c , d } . A move from ( a , b ) (a,b) ( a , b ) to ( b , a ) (b,a) ( b , a ) is a reversing move on { a , b } \{a,b\} { a , b } ; equivalently, it satisfies
g ( a , b ) = g ( b , a ) < g ( a , a ) = g ( b , b ) . g(a,b) = g(b,a) < g(a,a) = g(b,b). g ( a , b ) = g ( b , a ) < g ( a , a ) = g ( b , b ) . We say that Γ \Gamma Γ expresses a reversing move on { a , b } \{a,b\} { a , b } if such a function belongs to pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
The defining condition of a move is unchanged when a a a and b b b are swapped and, simultaneously, c c c and d d d are swapped. Hence a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) is also a move from ( b , a ) (b,a) ( b , a ) to ( d , c ) (d,c) ( d , c ) , and { a , b } ⇝ { c , d } \{a,b\} \leadsto\{c,d\} { a , b } ⇝ { c , d } holds if and only if there is a move to ( c , d ) (c,d) ( c , d ) from ( a , b ) (a,b) ( a , b ) or from ( b , a ) (b,a) ( b , a ) .
Now, we establish some further basic properties of moves, concretely that they are symmetric and compose, cf. [57 Lemma 5.1(b)] .
Lemma 4.3. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . If ( a , b ) ⇝ ( c , d ) (a,b) \leadsto(c,d) ( a , b ) ⇝ ( c , d ) , then ( c , d ) ⇝ ( a , b ) (c,d) \leadsto(a,b) ( c , d ) ⇝ ( a , b ) . Moreover, if there are finite-valued moves from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) and from ( c , d ) (c,d) ( c , d ) to ( x , y ) (x,y) ( x , y ) in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , and Γ \Gamma Γ expresses a restriction to { c , d } \{c,d\} { c , d } , then there is a finite-valued move from ( a , b ) (a,b) ( a , b ) to ( x , y ) (x,y) ( x , y ) in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Proof. Swapping the two arguments of a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) gives a move from ( c , d ) (c,d) ( c , d ) to ( a , b ) (a,b) ( a , b ) . For composition, let f , g ∈ pow ( Γ ) f,g \in\operatorname{pow}(\Gamma) f , g ∈ pow ( Γ ) be the two moves, with f ( a , c ) = f ( b , d ) = α < α ′ = f ( a , d ) = f ( b , c ) f(a,c)=f(b,d)=\alpha< \alpha' = f(a,d)=f(b,c) f ( a , c ) = f ( b , d ) = α < α ′ = f ( a , d ) = f ( b , c ) and g ( c , x ) = g ( d , y ) = β < β ′ = g ( c , y ) = g ( d , x ) g(c,x)=g(d,y)=\beta< \beta' = g(c,y)=g(d,x) g ( c , x ) = g ( d , y ) = β < β ′ = g ( c , y ) = g ( d , x ) . Let h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) be a restriction to { c , d } \{c,d\} { c , d } , shifted to be zero on { c , d } \{c,d\} { c , d } , and choose a rational λ > 0 \lambda> 0 λ > 0 with λ h ( z ) > max f + max g \lambda h(z) > \max f + \max g λh ( z ) > max f + max g for all z ∉ { c , d } z \notin\{c,d\} z ∈ / { c , d } . Then
k ( s , t ) = min z ∈ D ( f ( s , z ) + g ( z , t ) + λ h ( z ) ) k(s,t)=\min_{z\in D}\left(f(s,z)+g(z,t)+\lambda h(z)\right) k ( s , t ) = z ∈ D min ( f ( s , z ) + g ( z , t ) + λh ( z ) )
is a finite-valued function in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , and its minimum is always attained at some z ∈ { c , d } z \in\{c,d\} z ∈ { c , d } . Hence k ( a , x ) = k ( b , y ) = α + β < min { α + β ′ , α ′ + β } = k ( a , y ) = k ( b , x ) k(a,x)=k(b,y)=\alpha+\beta< \min\{\alpha+\beta',\alpha'+\beta\}=k(a,y)=k(b,x) k ( a , x ) = k ( b , y ) = α + β < min { α + β ′ , α ′ + β } = k ( a , y ) = k ( b , x ) , so k k k is a move from ( a , b ) (a,b) ( a , b ) to ( x , y ) (x,y) ( x , y ) .
Recall that our approach relies on a sequence of preprocessing steps. The first one concerns the domination of elements, defined as follows.
Definition 4.4 (Domination). Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . An element a ∈ D a \in D a ∈ D dominates an element b ∈ D b \in D b ∈ D if h ( a ) ≤ h ( b ) h(a) \le h(b) h ( a ) ≤ h ( b ) for every finite-valued unary cost function h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) .
For finite-valued hard-list languages, a dominated available element can be deleted when a distinct dominating element is also available at the same variable ((Lemma 6.1)). Crucially, two domain elements that do not dominate each other allow us to express all finite-valued unary cost functions on their pair.
Lemma 4.5. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . If distinct a , b ∈ D a,b \in D a , b ∈ D do not dominate each other, then Γ \Gamma Γ expresses all finite-valued unary cost functions on { a , b } \{a,b\} { a , b } .
Proof. By Definition 4.4, there are finite-valued unary functions h a , h b ∈ pow ( Γ ) h_a,h_b \in\operatorname{pow}(\Gamma) h a , h b ∈ pow ( Γ ) with h a ( a ) < h a ( b ) h_a(a)<h_a(b) h a ( a ) < h a ( b ) and h b ( b ) < h b ( a ) h_b(b)<h_b(a) h b ( b ) < h b ( a ) . Let u : { a , b } → Q ≥ 0 u:\{a,b\}\to\mathbb{Q}_{\ge0} u : { a , b } → Q ≥ 0 be an arbitrary function, and put δ = u ( b ) − u ( a ) \delta=u(b)-u(a) δ = u ( b ) − u ( a ) . If δ > 0 \delta>0 δ > 0 , scale h a h_a h a by δ / ( h a ( b ) − h a ( a ) ) \delta/(h_a(b)-h_a(a)) δ / ( h a ( b ) − h a ( a )) ; if δ < 0 \delta<0 δ < 0 , scale h b h_b h b by δ / ( h b ( b ) − h b ( a ) ) \delta/(h_b(b)-h_b(a)) δ / ( h b ( b ) − h b ( a )) ; and if δ = 0 \delta=0 δ = 0 , use the constant zero function. In every case the resulting finite-valued g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) satisfies g ( b ) − g ( a ) = δ g(b)-g(a)=\delta g ( b ) − g ( a ) = δ . Taking c = g ( a ) − u ( a ) c=g(a)-u(a) c = g ( a ) − u ( a ) gives g ( x ) = u ( x ) + c g(x)=u(x)+c g ( x ) = u ( x ) + c on x ∈ { a , b } x\in\{a,b\} x ∈ { a , b } .
The next preprocessing step we use concerns the separability of cost functions. For the definitions here, it suffices to focus on the binary case. Consider some cost function f f f of the constraint language. In principle, having a constraint in which f f f acts on two variables x x x and y y y couples these variables (which is expressed by an edge in the primal graph). However, if f ( x , y ) = u ( x ) + v ( y ) f(x,y)=u(x)+v(y) f ( x , y ) = u ( x ) + v ( y ) for two expressible unary cost functions u , v u,v u , v , then in an instance we can replace occurrences of f f f with two unary functions. If this is the case for all cost functions acting on both x x x and y y y , then we can preprocess the instance so that the remaining primal graph does not have an edge from x x x to y y y . Such functions f f f are also called separable [78 ] or modular [6 , 46 ] . More specifically, for a finite-valued binary cost function f f f , Helaoui and Naanaa call a , b a,b a , b a modular pair if f f f is modular on { a , b } × D \{a,b\}\times D { a , b } × D [46 ] . They show that this relation is an equivalence relation and exploit modular classes in search algorithms for binary VCSPs. We use this viewpoint to define interaction between domain elements and additionally impose non-domination conditions.
Definition 2.4 (Interacting pairs). Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . Distinct elements a , b ∈ D a,b \in D a , b ∈ D form an interacting pair if neither dominates the other and there are distinct elements c , d ∈ D c,d \in D c , d ∈ D , neither of which dominates the other, and a finite-valued binary cost function f ∈ pow ( Γ ) f \in\operatorname{pow}(\Gamma) f ∈ pow ( Γ ) such that
f ( a , c ) − f ( b , c ) ≠ f ( a , d ) − f ( b , d ) . f(a,c)-f(b,c) \ne f(a,d)-f(b,d). f ( a , c ) − f ( b , c ) = f ( a , d ) − f ( b , d ) . We say that { c , d } \{c,d\} { c , d } and f f f witness the interaction of a , b a,b a , b . A set is pairwise interacting if every pair of its distinct elements interacts. If two distinct elements do not interact, they form a noninteracting pair.
In our algorithm, we will decompose the instances based on noninteraction. For now, we focus on the opposite task: establishing properties we obtain based on interaction. First, we show that interaction gives a move to its witness pair, which explains the importance of this notion.
Lemma 4.6. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . Let a , b ∈ D a,b \in D a , b ∈ D have interaction witnessed by c , d c,d c , d and a finite-valued binary function f ∈ pow ( Γ ) f \in\operatorname{pow}(\Gamma) f ∈ pow ( Γ ) . If f ( a , c ) − f ( b , c ) < f ( a , d ) − f ( b , d ) f(a,c)-f(b,c)<f(a,d)-f(b,d) f ( a , c ) − f ( b , c ) < f ( a , d ) − f ( b , d ) , there is a finite-valued move ( a , b ) ⇝ ( c , d ) (a,b)\leadsto(c,d) ( a , b ) ⇝ ( c , d ) . Otherwise, there is a finite-valued move ( a , b ) ⇝ ( d , c ) (a,b)\leadsto(d,c) ( a , b ) ⇝ ( d , c ) . In any case, there is a finite-valued move { a , b } ⇝ { c , d } \{a,b\}\leadsto\{c,d\} { a , b } ⇝ { c , d } .
Proof. For unary functions u , v u,v u , v , the function g ( x , y ) = f ( x , y ) + u ( x ) + v ( y ) g(x,y)=f(x,y)+u(x)+v(y) g ( x , y ) = f ( x , y ) + u ( x ) + v ( y ) satisfies
g ( a , c ) + g ( b , d ) − g ( a , d ) − g ( b , c ) = f ( a , c ) + f ( b , d ) − f ( a , d ) − f ( b , c ) = : Δ , g(a,c)+g(b,d)-g(a,d)-g(b,c)=f(a,c)+f(b,d)-f(a,d)-f(b,c)=:\Delta, g ( a , c ) + g ( b , d ) − g ( a , d ) − g ( b , c ) = f ( a , c ) + f ( b , d ) − f ( a , d ) − f ( b , c ) =: Δ ,
and Δ ≠ 0 \Delta\ne0 Δ = 0 by the witness assumption. Since neither element of { a , b } \{a,b\} { a , b } , nor of { c , d } \{c,d\} { c , d } , dominates the other, Lemma 4.5 gives finite-valued unary u , v ∈ pow ( Γ ) u,v\in\operatorname{pow}(\Gamma) u , v ∈ pow ( Γ ) with
u ( b ) − u ( a ) = 1 2 ( f ( a , c ) − f ( b , d ) + f ( a , d ) − f ( b , c ) ) , u(b)-u(a)=\frac{1}{2}\left(f(a,c)-f(b,d)+f(a,d)-f(b,c)\right), u ( b ) − u ( a ) = 2 1 ( f ( a , c ) − f ( b , d ) + f ( a , d ) − f ( b , c ) ) ,
v ( d ) − v ( c ) = 1 2 ( f ( a , c ) − f ( b , d ) − f ( a , d ) + f ( b , c ) ) . v(d)-v(c)=\frac{1}{2}\left(f(a,c)-f(b,d)-f(a,d)+f(b,c)\right). v ( d ) − v ( c ) = 2 1 ( f ( a , c ) − f ( b , d ) − f ( a , d ) + f ( b , c ) ) .
This choice makes g ( a , c ) = g ( b , d ) g(a,c)=g(b,d) g ( a , c ) = g ( b , d ) and g ( a , d ) = g ( b , c ) g(a,d)=g(b,c) g ( a , d ) = g ( b , c ) , so g ( a , c ) − g ( a , d ) = Δ / 2 g(a,c)-g(a,d)=\Delta/2 g ( a , c ) − g ( a , d ) = Δ/2 . Hence the finite-valued function g g g is a move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) if Δ < 0 \Delta<0 Δ < 0 , that is, if f ( a , c ) − f ( b , c ) < f ( a , d ) − f ( b , d ) f(a,c)-f(b,c)<f(a,d)-f(b,d) f ( a , c ) − f ( b , c ) < f ( a , d ) − f ( b , d ) , and a move from ( a , b ) (a,b) ( a , b ) to ( d , c ) (d,c) ( d , c ) otherwise. Similar normalizations appear in the proofs of [57 Lemma 5.1(b)] and [79 Lemma 2.4] .
Having established the required moves based on interaction, we turn to expressing all finite-valued cost functions, first on a two-element set and then on larger sets.
Lemma 4.7. Let D D D be a finite domain, Γ \Gamma Γ a constraint language over D D D , and P = { p , q } ⊆ D P=\{p,q\}\subseteq D P = { p , q } ⊆ D with p ≠ q p\ne q p = q . Suppose that Γ \Gamma Γ expresses all finite-valued unary cost functions on P P P , a finite-valued reversing move on P P P , and a restriction to P P P . Then Γ \Gamma Γ expresses all finite-valued cost functions on P P P .
Proof. Identify p , q p,q p , q with 0 , 1 0,1 0 , 1 , and let h ∈ pow ( Γ ) h\in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) be a restriction to P P P , shifted to be zero on P P P . Every auxiliary variable below is forced into P P P by adding λ h \lambda h λh for a sufficiently large rational λ \lambda λ . All other terms are finite-valued, so this keeps the expressed functions finite-valued, and for inputs in P P P they agree with the displayed expressions up to additive constants.
Rescaling the reversing move gives e ∈ pow ( Γ ) e\in\operatorname{pow}(\Gamma) e ∈ pow ( Γ ) with e ( s , t ) = 1 e(s,t)=1 e ( s , t ) = 1 for s = t s=t s = t and e ( s , t ) = 0 e(s,t)=0 e ( s , t ) = 0 for s ≠ t s\ne t s = t , on P 2 P^2 P 2 and up to a constant. Its complement is
1 − e ( s , t ) = min z ∈ P ( 2 e ( s , z ) + e ( z , t ) ) , 1-e(s,t)=\min_{z\in P}\left(2e(s,z)+e(z,t)\right), 1 − e ( s , t ) = z ∈ P min ( 2 e ( s , z ) + e ( z , t ) ) ,
since the minimum is attained at z ≠ s z\ne s z = s . On P 2 P^2 P 2 we have
s t = 1 2 ( e ( s , t ) + s + t − 1 ) , − s t = 1 2 ( 1 − e ( s , t ) − s − t ) . st=\frac{1}{2}\left(e(s,t)+s+t-1\right),\qquad-st=\frac{1}{2}\left(1-e(s,t)-s-t\right). s t = 2 1 ( e ( s , t ) + s + t − 1 ) , − s t = 2 1 ( 1 − e ( s , t ) − s − t ) .
Together with the unary functions on P P P , these give every polynomial of degree at most two in variables ranging over P P P , up to a constant. In particular, Γ \Gamma Γ expresses all finite-valued unary and binary cost functions on P P P .
Let r ≥ 1 r\ge1 r ≥ 1 and f : P r → Q ≥ 0 f:P^r\to\mathbb{Q}_{\ge0} f : P r → Q ≥ 0 . By [19 Theorem 28] , f f f can be expressed using finite-valued unary and binary cost functions on P P P . Replace each cost function in such a gadget by its finite-valued representative in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , and restrict its auxiliary variables to P P P as above. The resulting function belongs to pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) and agrees with f f f up to a constant on P r P^r P r . It is finite-valued on all of D r D^r D r , since every input assignment admits a finite-cost extension with all auxiliary variables in P P P .
Lemma 4.8. Let D D D be a finite domain, Γ \Gamma Γ a constraint language over D D D , and P = { p , q } ⊆ D P=\{p,q\}\subseteq D P = { p , q } ⊆ D with p ≠ q p\ne q p = q . Let r ≥ 1 r\ge1 r ≥ 1 and let S 1 , … , S r ⊆ D S_1,\ldots,S_r\subseteq D S 1 , … , S r ⊆ D be nonempty subsets. Suppose that Γ \Gamma Γ expresses all finite-valued cost functions on P P P and all finite-valued unary cost functions on each S i S_i S i . Assume that Γ \Gamma Γ expresses a restriction to P P P . Suppose further that there is a finite-valued move m ( a , b ) ↦ ( p , q ) ∈ pow ( Γ ) m_{(a,b)\mapsto(p,q)}\in\operatorname{pow}(\Gamma) m ( a , b ) ↦ ( p , q ) ∈ pow ( Γ ) for every two distinct elements a , b ∈ S i a,b\in S_i a , b ∈ S i , for each i i i . For every f : S 1 × ⋯ × S r → Q ≥ 0 f:S_1\times\cdots\times S_r\to\mathbb{Q}_{\ge0} f : S 1 × ⋯ × S r → Q ≥ 0 , there are a finite-valued g ∈ pow ( Γ ) g\in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c\in\mathbb{Q} c ∈ Q with g ( x ˉ ) = f ( x ˉ ) + c g(\bar{x})=f(\bar{x})+c g ( x ˉ ) = f ( x ˉ ) + c on x ˉ ∈ S 1 × ⋯ × S r \bar{x}\in S_1\times\cdots\times S_r x ˉ ∈ S 1 × ⋯ × S r .
Proof. Coordinates i ∈ [ r ] i\in[r] i ∈ [ r ] with ∣ S i ∣ = 1 |S_i|=1 ∣ S i ∣ = 1 can be substituted in f f f and then ignored in the gadget. If every S i S_i S i has size one, f f f is constant on S 1 × ⋯ × S r S_1\times\cdots\times S_r S 1 × ⋯ × S r , and the zero-cost gadget suffices. We may therefore assume that each S i S_i S i has at least two elements.
For each i ∈ [ r ] i\in[r] i ∈ [ r ] and each pair of distinct elements a , b ∈ S i a,b\in S_i a , b ∈ S i , choose an ordering ( a , b ) (a,b) ( a , b ) and a finite-valued move m ( a , b ) ↦ ( p , q ) ∈ pow ( Γ ) m_{(a,b)\mapsto(p,q)}\in\operatorname{pow}(\Gamma) m ( a , b ) ↦ ( p , q ) ∈ pow ( Γ ) from ( a , b ) (a,b) ( a , b ) to ( p , q ) (p,q) ( p , q ) . Let S i S_i S i be the set of the chosen ordered pairs of S i S_i S i , and put k i = ∣ S i ∣ = ( ∣ S i ∣ 2 ) k_i=|S_i|=\binom{|S_i|}{2} k i = ∣ S i ∣ = ( 2 ∣ S i ∣ ) . For each i i i , we use a common input variable x i x_i x i and a separate output variable z i , ( a , b ) z_{i,(a,b)} z i , ( a , b ) for each ( a , b ) ∈ S i (a,b)\in S_i ( a , b ) ∈ S i . Fix an ordering of S i S_i S i and write z ˉ i = ( z i , ( a , b ) ) ( a , b ) ∈ S i \bar{z}_i=(z_{i,(a,b)})_{(a,b)\in S_i} z ˉ i = ( z i , ( a , b ) ) ( a , b ) ∈ S i . Define the finite-valued cost function H i ∈ pow ( Γ ) H_i\in\operatorname{pow}(\Gamma) H i ∈ pow ( Γ ) by
H i ( x i , z ˉ i ) = ∑ ( a , b ) ∈ S i m ( a , b ) ⇝ ( p , q ) ( x i , z i , ( a , b ) ) . H_i(x_i,\bar{z}_i)=\sum_{(a,b)\in S_i}m_{(a,b)\leadsto(p,q)}(x_i,z_{i,(a,b)}). H i ( x i , z ˉ i ) = ( a , b ) ∈ S i ∑ m ( a , b ) ⇝ ( p , q ) ( x i , z i , ( a , b ) ) .
That is, we sum up over all moves from S i S_i S i to P P P and identify the first variable while keeping the second variable of each move separate. Intuitively, the first variable x i x_i x i is the input of H i H_i H i and the variables z ˉ i \bar{z}_i z ˉ i are the output variables. For each pair { a , b } \{a,b\} { a , b } of elements of S i S_i S i the function has one dedicated output variable.
We will force every output variable to lie in P P P once the rest of the gadget is constructed. Write
M i ( a ) = min z ˉ ∈ P k i H i ( a , z ˉ ) , M_i(a)=\min_{\bar{z}\in P^{k_i}}H_i(a,\bar{z}), M i ( a ) = z ˉ ∈ P k i min H i ( a , z ˉ ) ,
for the minimum cost obtainable when assigning domain element a a a to the input of the construction for i i i . For each a ∈ S i a\in S_i a ∈ S i select a minimizing tuple z ˉ i ( a ) ∈ P k i \bar{z}_i(a)\in P^{k_i} z ˉ i ( a ) ∈ P k i , i.e., a tuple z ˉ i ( a ) \bar{z}_i(a) z ˉ i ( a ) such that H i ( a , z ˉ i ( a ) ) = M i ( a ) H_i(a,\bar{z}_i(a))=M_i(a) H i ( a , z ˉ i ( a )) = M i ( a ) . The output variable z i , ( a , b ) z_{i,(a,b)} z i , ( a , b ) has different unique minimizing values for inputs a a a and b b b due to the move m ( a , b ) ⇝ ( p , q ) m_{(a,b)\leadsto(p,q)} m ( a , b ) ⇝ ( p , q ) acting on it. Since all the moves used in the construction have separate outputs, their minima are attained independently. Consequently, there is no assignment z ˉ ∈ P k i \bar{z}\in P^{k_i} z ˉ ∈ P k i to the outputs that minimizes H i H_i H i for two distinct inputs a , b ∈ S i a,b\in S_i a , b ∈ S i . Hence,
δ i = min a , b ∈ S i a ≠ b ( H i ( a , z ˉ i ( b ) ) − M i ( a ) ) > 0. \delta_i=\min_{\substack{a,b\in S_i\\a\ne b}}\left(H_i(a,\bar{z}_i(b))-M_i(a)\right)>0. δ i = a , b ∈ S i a = b min ( H i ( a , z ˉ i ( b )) − M i ( a ) ) > 0.
In particular, the selected tuples z ˉ i ( a ) \bar{z}_i(a) z ˉ i ( a ) are all distinct.
So far, we ensured that for any two distinct assignments to the input variables that come from the domain S 1 × ⋯ × S r S_1\times\cdots\times S_r S 1 × ⋯ × S r , the sets of assignments to the output variables, restricted to assignments using domain elements of P P P , that minimize the cost of the constructed gadget do not intersect. However, it may still be the case that certain inputs are cheaper overall than others.
To mitigate this, use the assumed unary expressibility on each S i S_i S i to add, up to constants, the nonnegative unary costs
max a ∈ S i M i ( a ) − M i ( x i ) on S i . \max_{a\in S_i}M_i(a)-M_i(x_i)\quad\text{on }S_i. a ∈ S i max M i ( a ) − M i ( x i ) on S i .
These normalize the input-dependent minima, guaranteeing that all possible assignments from S i S_i S i to input variable x i x_i x i have the same cost C i C_i C i when using intended assignments to the outputs. Call the gadget created for S i S_i S i so far the encoding gadget for S i S_i S i .
Put R = max f R=\max f R = max f and choose positive rational weights λ i \lambda_i λ i with λ i δ i > R \lambda_i\delta_i>R λ i δ i > R . We weigh each used encoding gadget with λ i \lambda_i λ i . This will ensure that, for input assignment a ∈ S i a\in S_i a ∈ S i , it comes with a significant cost to assign a tuple z ˉ i ( b ) \bar{z}_i(b) z ˉ i ( b ) for b ∈ S i ∖ { a } b\in S_i\setminus\{a\} b ∈ S i ∖ { a } to the outputs.
Next, we will use the expressibility on P P P to ensure the overall gadget expresses the function f f f on the intended domain. By this assumed expressibility, express on the concatenated output tuples z ˉ 1 , … , z ˉ r \bar{z}_1,\ldots,\bar{z}_r z ˉ 1 , … , z ˉ r the function that has value
f ( a 1 , … , a r ) at ( z ˉ 1 ( a 1 ) , … , z ˉ r ( a r ) ) f(a_1,\ldots,a_r)\quad\text{at }\bigl(\bar{z}_1(a_1),\ldots,\bar{z}_r(a_r)\bigr) f ( a 1 , … , a r ) at ( z ˉ 1 ( a 1 ) , … , z ˉ r ( a r ) )
and value R + 1 R+1 R + 1 at every other tuple in P k 1 + ⋯ + k r P^{k_1+\cdots+k_r} P k 1 + ⋯ + k r .
First consider minimizing the resulting gadget with all outputs taking values from P P P . For inputs x i ∈ S i x_i\in S_i x i ∈ S i , their selected tuples z ˉ i ( x i ) \bar{z}_i(x_i) z ˉ i ( x i ) attain, up to a common constant, the value
∑ i λ i C i + f ( x 1 , … , x r ) , \sum_i\lambda_i C_i+f(x_1,\ldots,x_r), i ∑ λ i C i + f ( x 1 , … , x r ) ,
where the cost ∑ i λ i C i \sum_i\lambda_i C_i ∑ i λ i C i stems from the encoding gadgets and the cost of f f f from the function we added in the previous step. Any selected tuple belonging to a different input (i.e., for some i ∈ [ r ] i\in[r] i ∈ [ r ] the assignment to the output variables z ˉ i \bar{z}_i z ˉ i is z ˉ i ( b ) \bar{z}_i(b) z ˉ i ( b ) for some b ∈ S i b\in S_i b ∈ S i different from the assignment to x i x_i x i ) costs more than ∑ i λ i C i + R \sum_i\lambda_i C_i+R ∑ i λ i C i + R , because at least one of the encoding gadgets incurs a gap λ i δ i > R \lambda_i\delta_i>R λ i δ i > R . Every tuple not selected for any input (i.e., for some i ∈ [ r ] i\in[r] i ∈ [ r ] the assignment to the output variables z ˉ i \bar{z}_i z ˉ i is not of the form z ˉ i ( b ) \bar{z}_i(b) z ˉ i ( b ) for any b ∈ S i b\in S_i b ∈ S i ) pays the penalty R + 1 R+1 R + 1 in addition to the cost due to the encoding gadgets, which is itself at least ∑ i λ i C i \sum_i\lambda_i C_i ∑ i λ i C i . Hence neither kind of tuple can improve on the variable assignment intended for the actual input.
Finally, we need to ensure that all of the output variables take a value from P P P . Let h ∈ pow ( Γ ) h\in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) be a restriction to P P P which exists by assumption, shifted so that it is zero on P P P . Let F F F be the cost function of the gadget constructed so far. Choose a positive rational W W W such that W h ( d ) > max F W h(d) > \max F W h ( d ) > max F for every d ∉ P d \notin P d ∈ / P . Add W h W h W h at every output variable. As in the proof of Lemma 4.7, this makes the minimum attained with all outputs in P P P . The restrictions act only on auxiliary variables, and every assignment to the exposed inputs has a finite extension with all outputs in P P P . So, the resulting function is finite-valued on D r D^r D r .
VCSP over Finite-Valued Soft-List Languages
We now apply the results on interaction and moves to finite-valued soft-list languages. Let us first recall the central definitions surrounding soft lists.
Definition 3.6 (Soft lists and soft-list languages). Let B ⊆ D B \subseteq D B ⊆ D . The soft list on B B B is the unary cost function
h B ( d ) = { 0 , d ∈ B , 1 , d ∉ B . h_B(d) =
\begin{cases}
0, & d \in B,\\
1, & d \notin B.
\end{cases} h B ( d ) = { 0 , 1 , d ∈ B , d ∈ / B . We say that Γ \Gamma Γ expresses all soft lists if h B ∈ pow ( Γ ) h_B \in\operatorname{pow}(\Gamma) h B ∈ pow ( Γ ) for every B ⊆ D B \subseteq D B ⊆ D . If h B ∈ Γ h_B \in\Gamma h B ∈ Γ for every B ⊆ D B \subseteq D B ⊆ D , we say that Γ \Gamma Γ contains all soft lists.
For B ⊆ D B \subseteq D B ⊆ D , we say that Γ \Gamma Γ expresses all soft lists on B B B if, for every S ⊆ B S \subseteq B S ⊆ B , there is a finite-valued unary function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c \in\mathbb{Q} c ∈ Q such that g ( d ) = h S ( d ) + c g(d) = h_S(d) + c g ( d ) = h S ( d ) + c for every d ∈ B d \in B d ∈ B .
We call a finite constraint language Γ \Gamma Γ over D D D a soft-list language if, for every d ∈ D d \in D d ∈ D , Γ \Gamma Γ contains the unary cost function that takes value 1 1 1 at d d d and 0 0 0 at every other element of D D D .
Every finite-valued soft-list language expresses all soft lists: h B h_B h B is the sum, over d ∈ D ∖ B d \in D \setminus B d ∈ D ∖ B , of the unary functions taking value 1 1 1 at d d d and 0 0 0 elsewhere.
We will show that if two elements of the domain are equivalent in some sense, then we can preprocess one of them away. Once we are left with an instance in which no two remaining elements are equivalent, we show a matching lower bound. Intuitively, two elements d 1 d_1 d 1 and d 2 d_2 d 2 are equivalent if replacing d 1 d_1 d 1 with d 2 d_2 d 2 in any constraint changes the cost by a fixed constant that depends only on the ordered pair d 1 , d 2 d_1,d_2 d 1 , d 2 , the cost function, and the position of the element in the constraint.
Definition 5.1 (Additive equivalence). Two elements d 1 , d 2 ∈ D d_1,d_2 \in D d 1 , d 2 ∈ D are additively equivalent if, for each f ∈ Γ f \in\Gamma f ∈ Γ and each i ∈ { 1 , … , arity ( f ) } i \in\{1,\ldots,\operatorname{arity}(f)\} i ∈ { 1 , … , arity ( f )} , there is a constant c f , i d 1 , d 2 ∈ Q c_{f,i}^{d_1,d_2} \in\mathbb{Q} c f , i d 1 , d 2 ∈ Q such that, for all w 1 , … , w arity ( f ) − 1 ∈ D w_1,\ldots,w_{\operatorname{arity}(f)-1} \in D w 1 , … , w arity ( f ) − 1 ∈ D , we have
f ( w 1 , … , w i − 1 , d 1 , w i , … , w arity ( f ) − 1 ) = f ( w 1 , … , w i − 1 , d 2 , w i , … , w arity ( f ) − 1 ) + c f , i d 1 , d 2 . f(w_1,\ldots,w_{i-1},d_1,w_i,\ldots,w_{\operatorname{arity}(f)-1}) = f(w_1,\ldots,w_{i-1},d_2,w_i,\ldots,w_{\operatorname{arity}(f)-1}) + c_{f,i}^{d_1,d_2}. f ( w 1 , … , w i − 1 , d 1 , w i , … , w arity ( f ) − 1 ) = f ( w 1 , … , w i − 1 , d 2 , w i , … , w arity ( f ) − 1 ) + c f , i d 1 , d 2 . If d 1 d_1 d 1 and d 2 d_2 d 2 are additively equivalent we also write d 1 ≡ Γ d 2 d_1 \equiv_\Gamma d_2 d 1 ≡ Γ d 2 . We call c f , i d 1 , d 2 c_{f,i}^{d_1,d_2} c f , i d 1 , d 2 a constant witnessing d 1 ≡ Γ d 2 d_1 \equiv_\Gamma d_2 d 1 ≡ Γ d 2 for f f f and position $i.
Clearly, additive equivalence defines an equivalence relation.
Lemma 5.2. Let D D D be a domain and Γ \Gamma Γ a constraint language over D D D . Then, ≡ Γ \equiv_\Gamma ≡ Γ is an equivalence relation.
Proof. The constants c f , i d , d = 0 c_{f,i}^{d,d} = 0 c f , i d , d = 0 , c f , i d 2 , d 1 = − c f , i d 1 , d 2 c_{f,i}^{d_2,d_1} = -c_{f,i}^{d_1,d_2} c f , i d 2 , d 1 = − c f , i d 1 , d 2 , and c f , i d 1 , d 3 = c f , i d 1 , d 2 + c f , i d 2 , d 3 c_{f,i}^{d_1,d_3} = c_{f,i}^{d_1,d_2} + c_{f,i}^{d_2,d_3} c f , i d 1 , d 3 = c f , i d 1 , d 2 + c f , i d 2 , d 3 witness reflexivity, symmetry, and transitivity, respectively.
The Algorithm
Now, let us work towards obtaining our algorithm. First, we can show that if two distinct elements are additively equivalent, we can delete one of them without changing the problem.
Lemma 5.3. Let D D D be a fixed finite domain and Γ \Gamma Γ a finite-valued soft-list language over D D D . Suppose that two distinct elements d 1 , d 2 ∈ D d_1,d_2 \in D d 1 , d 2 ∈ D are additively equivalent. Then VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) and VCSP ( Γ ′ ) \operatorname{VCSP}(\Gamma') VCSP ( Γ ′ ) are equivalent under polynomial-time reductions, where Γ ′ \Gamma' Γ ′ is obtained by restricting each cost function in Γ \Gamma Γ to D ∖ { d 1 } D \setminus\{d_1\} D ∖ { d 1 } . Moreover, the reductions do not change the primal graph of the instances.
Proof. Restricting the unary functions that take value 1 1 1 on one element and 0 0 0 elsewhere shows that Γ ′ \Gamma' Γ ′ is again a finite-valued soft-list language. For each f ∈ Γ f \in\Gamma f ∈ Γ and each position i i i , fix a constant c f , i d 1 , d 2 c_{f,i}^{d_1,d_2} c f , i d 1 , d 2 witnessing d 1 ≡ Γ d 2 d_1 \equiv_\Gamma d_2 d 1 ≡ Γ d 2 for f f f and position i i i (as defined in Definition 5.1). Thus, changing the entry in position i i i from d 2 d_2 d 2 to d 1 d_1 d 1 adds c f , i d 1 , d 2 c_{f,i}^{d_1,d_2} c f , i d 1 , d 2 to the cost, independently of the other entries.
Now, consider an instance I = ( V , C , t ) I=(V,C,t) I = ( V , C , t ) of VCSP(Γ \Gamma Γ ). For each variable v ∈ V v \in V v ∈ V , we can determine whether it is better to assign d 1 d_1 d 1 or d 2 d_2 d 2 to v v v , independently of the assignments to the other variables. To do this, let C v C_v C v be the constraints with v v v in their scope, and calculate
Δ v = ∑ C ∈ C v weight ( C ) ∑ i : scope ( C ) i = v c cost ( C ) , i d 1 , d 2 . \Delta_v=\sum_{C\in C_v}\operatorname{weight}(C)\sum_{i:\operatorname{scope}(C)_i=v} c_{\operatorname{cost}(C),i}^{d_1,d_2}. Δ v = C ∈ C v ∑ weight ( C ) i : scope ( C ) i = v ∑ c cost ( C ) , i d 1 , d 2 .
where scope ( C ) i = v \operatorname{scope}(C)_i=v scope ( C ) i = v expresses that v v v is the i i i th element of the scope of C C C . The inner sum runs over all positions where v v v occurs in the scope of C C C , which ensures that repeated occurrences of v v v within a single constraint are counted separately.
Consider a variable assignment π \pi π with π ( v ) = d 1 \pi(v)=d_1 π ( v ) = d 1 , and obtain π ′ \pi' π ′ by changing only the assignment of v v v to d 2 d_2 d 2 . By Definition 5.1 , the cost of π \pi π equals the cost of π ′ \pi' π ′ plus Δ v \Delta_v Δ v . This follows by replacing the occurrences of v v v one at a time and adding the corresponding weighted witnessing constants. Hence, we prefer d 2 d_2 d 2 if Δ v ≥ 0 \Delta_v \ge0 Δ v ≥ 0 , and d 1 d_1 d 1 if Δ v < 0 \Delta_v < 0 Δ v < 0 .
In the output instance, we restrict all original cost functions to D ∖ { d 1 } D \setminus\{d_1\} D ∖ { d 1 } and keep their scopes and weights. For each variable v v v with Δ v < 0 \Delta_v < 0 Δ v < 0 , we add the soft list on { d 2 } \{d_2\} { d 2 } at v v v with weight − Δ v -\Delta_v − Δ v . Thus, the added cost at v v v is − Δ v -\Delta_v − Δ v unless v v v is assigned d 2 d_2 d 2 , in which case it is zero. We set the target to
t ′ = t + ∑ v : Δ v < 0 ( − Δ v ) . t'=t+\sum_{v:\Delta_v<0}(-\Delta_v). t ′ = t + v : Δ v < 0 ∑ ( − Δ v ) .
For variables with Δ v ≥ 0 \Delta_v \ge0 Δ v ≥ 0 , we add no constraints. All added penalties are implemented by weighted unary constraints from Γ ′ \Gamma' Γ ′ as described after the statement of Definition 3.6 in § 5 .
To see that the reduction is correct, consider an assignment π \pi π of the input instance of cost at most t t t . We may assume that whenever a variable is assigned one of d 1 , d 2 d_1,d_2 d 1 , d 2 , it is assigned the preferred one. We then replace every occurrence of d 1 d_1 d 1 by d 2 d_2 d 2 to create π ′ \pi' π ′ . For a variable v v v with Δ v < 0 \Delta_v < 0 Δ v < 0 , this increases the cost by − Δ v -\Delta_v − Δ v if v v v was assigned d 1 d_1 d 1 . If v v v was assigned any other element, it also increases the cost by − Δ v -\Delta_v − Δ v due to the added unary penalty of − Δ v -\Delta_v − Δ v . Variables with Δ v ≥ 0 \Delta_v \ge0 Δ v ≥ 0 contribute no change. Altogether, the cost of π ′ \pi' π ′ is exactly the cost of π \pi π plus t ′ − t t'-t t ′ − t . Therefore, π ′ \pi' π ′ is an assignment of the output instance of cost at most t ′ t' t ′ .
Conversely, take an output assignment π ′ \pi' π ′ of cost at most t ′ t' t ′ . For each variable v v v with Δ v < 0 \Delta_v < 0 Δ v < 0 that is assigned d 2 d_2 d 2 , change its assignment to d 1 d_1 d 1 to create assignment π \pi π . This decreases the cost of the original constraints by − Δ v -\Delta_v − Δ v . If such a variable is assigned another element, keep its assignment. Since the input instance does not contain its added unary penalty, again this decreases the cost by − Δ v -\Delta_v − Δ v . The resulting input assignment π \pi π therefore has cost at most t ′ − ( t ′ − t ) = t t'-(t'-t)=t t ′ − ( t ′ − t ) = t .
For the reduction in the other direction, that is, from VCSP(Γ ′ \Gamma' Γ ′ ) to VCSP(Γ \Gamma Γ ), we only need to make sure that no variable is assigned the domain value d 1 d_1 d 1 . Lift each constraint to its original cost function in Γ \Gamma Γ , and use a unary constraint to penalize assigning d 1 d_1 d 1 at any variable by max { 0 , t } + 1 \max\{0,t\}+1 max { 0 , t } + 1 (to keep the penalty positive when t t t is negative), while not penalizing other assignments. An assignment to the input instance then gives an assignment to the output instance of the same cost. Since all costs are nonnegative, an assignment to the output instance of cost at most t t t cannot use d 1 d_1 d 1 . Hence, it again gives an assignment to the input instance of the same cost.
It is clear from the description of the reductions that they run in polynomial time, and that they do not change the primal graph.
Theorem 5.4. Let D D D be a fixed finite domain and Γ \Gamma Γ a finite-valued soft-list language over D D D . Let q Γ q_{\Gamma} q Γ be the number of equivalence classes of ≡ Γ \equiv_{\Gamma} ≡ Γ . Given as input I I I an instance of VCSP(Γ \Gamma Γ ) and a tree decomposition T T T of its primal graph of width tw \operatorname{tw} tw , VCSP(Γ \Gamma Γ ) can be solved in time ( q Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) (q_{\Gamma})^{\operatorname{tw}}\cdot(|I|+|T|)^{O(1)} ( q Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) .
Proof. Use the reduction of Lemma 5.3 repeatedly until the domain of the obtained instance is D ′ D' D ′ , where D ′ D' D ′ contains exactly one element of each equivalence class of ≡ Γ \equiv_{\Gamma} ≡ Γ . The reductions preserve the primal graph, so the supplied tree decomposition remains valid. Every variable of the reduced instance has available set D ′ D' D ′ , of size q Γ q_{\Gamma} q Γ . Thus Lemma 2.8 gives the claimed running time. ∎
The Lower Bound
Now, we show a lower bound matching Theorem 5.4. Recall that we want to state our lower bounds in terms of a constant c Γ c_{\Gamma} c Γ depending on the size of a domain subset on which we can express binary disequality. For this purpose, let us formally define this constant.
Definition 5.5 (Running time base c Γ c_{\Gamma} c Γ ). Let D D D be a finite domain and Γ \Gamma Γ be a constraint language over D D D . For a subset D ′ ⊆ D D' \subseteq D D ′ ⊆ D a binary function f f f with f ( x , y ) = 0 f(x,y)=0 f ( x , y ) = 0 for x , y ∈ D ′ x,y \in D' x , y ∈ D ′ with x ≠ y x \ne y x = y , and f ( x , x ) = 1 f(x,x)=1 f ( x , x ) = 1 for x ∈ D ′ x \in D' x ∈ D ′ is a binary disequality function on D ′ D' D ′ . We define c Γ c_{\Gamma} c Γ to be the maximum cardinality of a subset D ′ ⊆ D D' \subseteq D D ′ ⊆ D such that Γ \Gamma Γ expresses a binary disequality function on D ′ D' D ′ .
It is quite easy to obtain a lower bound using the running time base c Γ c_{\Gamma} c Γ , indeed if c Γ = 2 c_{\Gamma}=2 c Γ = 2 a reduction from Max Cut, and if c Γ ≥ 3 c_{\Gamma}\ge3 c Γ ≥ 3 a reduction from c Γ c_{\Gamma} c Γ -Coloring suffices.
Lemma 5.6. Let D D D be a fixed finite domain and Γ \Gamma Γ be a fixed constraint language over D D D . Let D ′ ⊆ D D' \subseteq D D ′ ⊆ D be a set of size c Γ c_{\Gamma} c Γ such that Γ \Gamma Γ expresses a binary disequality function f f f on D ′ D' D ′ . Assume that Γ \Gamma Γ additionally expresses a restriction to D ′ D' D ′ , and that c Γ ≥ 2 c_{\Gamma}\ge2 c Γ ≥ 2 . Then, for every ε > 0 \varepsilon>0 ε > 0 , there is no algorithm solving VCSP( Γ ) (\Gamma) ( Γ ) in time
( c Γ − ε ) p w ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (c_{\Gamma}-\varepsilon)^{\mathrm{pw}}\cdot(|I|+|\mathcal{T}|)^{O(1)}, ( c Γ − ε ) pw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , where the input consists of an instance I I I and a path decomposition T \mathcal{T} T of its primal graph of width p w \mathrm{pw} pw , unless pw-SETH is false. The same lower bound holds with pathwidth replaced by treewidth under tw-SETH.
Proof. By shifting and scaling the expressed restriction to D ′ D' D ′ , fix h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) with h ( d ) = 0 h(d)=0 h ( d ) = 0 for d ∈ D ′ d \in D' d ∈ D ′ and h ( d ) ≥ 1 h(d)\ge1 h ( d ) ≥ 1 for d ∉ D ′ d \notin D' d ∈ / D ′ .
Given a graph G = ( V , E ) G=(V,E) G = ( V , E ) with m = ∣ E ∣ m=|E| m = ∣ E ∣ , construct an instance over Γ ∪ { f , h } \Gamma\cup\{f,h\} Γ ∪ { f , h } with variable set V V V . For every edge u v ∈ E uv \in E uv ∈ E , add the constraint ( f , ( u , v ) , 1 ) (f,(u,v),1) ( f , ( u , v ) , 1 ) , choosing either ordering of its endpoints, and for every v ∈ V v \in V v ∈ V , add ( h , ( v ) , m + 1 ) (h,(v),m+1) ( h , ( v ) , m + 1 ) . An assignment where a variable uses a value outside D ′ D' D ′ has cost at least m + 1 m+1 m + 1 due to this restriction, whereas every assignment over D ′ D' D ′ has cost at most m m m . For an assignment π : V → D ′ \pi:V\to D' π : V → D ′ , the cost is exactly
∣ { u v ∈ E : π ( u ) = π ( v ) } ∣ . \left|\{uv \in E:\pi(u)=\pi(v)\}\right|. ∣ { uv ∈ E : π ( u ) = π ( v )} ∣ .
If c Γ = 2 c_{\Gamma}=2 c Γ = 2 , a Max Cut instance asking for a cut of size at least k k k , where 0 ≤ k ≤ m 0\le k\le m 0 ≤ k ≤ m , is therefore equivalent to the constructed instance with target m − k m-k m − k . If c Γ ≥ 3 c_{\Gamma}\ge3 c Γ ≥ 3 , the graph G G G has a proper c Γ c_{\Gamma} c Γ -coloring if and only if the constructed instance with target zero is a yes-instance.
The constructed instance has the same primal graph as G G G . Since { f , h } \{f,h\} { f , h } is a fixed finite subset of pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , Lemma 3.2 replaces these functions by gadgets over Γ \Gamma Γ in polynomial time, adjusts the target, and increases the width of the supplied path or tree decomposition by at most a constant.
For c Γ = 2 c_{\Gamma}=2 c Γ = 2 , the corresponding lower bound for Max Cut under tw-SETH follows from [48 Theorem 1] and the reduction in [60 Claim 5.2] . For pw-SETH, the lower bound follows from the Max-2-SAT lower bound in [58 Theorem 3.1] , together with the reduction in [60 Claim 5.2] , which also only increases the pathwidth by a constant. For c Γ ≥ 3 c_{\Gamma}\ge3 c Γ ≥ 3 , the required lower bounds for c Γ c_{\Gamma} c Γ -Coloring follow from [58 Lemma 5.1] under pw-SETH and from [60 Claims 5.3–5.4] under tw-SETH. Thus, in both cases, an algorithm with the stated running time would contradict the corresponding hypothesis.
:::
Hence, the remainder of this section is dedicated to showing that c Γ = q Γ c_{\Gamma}=q_{\Gamma} c Γ = q Γ , assuming that c Γ ≥ 2 c_{\Gamma}\ge2 c Γ ≥ 2 . For this purpose, we show that all finite-valued cost functions on the domain remaining after preprocessing can be expressed, up to a common additive constant. We begin by showing this for unary cost functions.
Lemma 5.7. Let D D D be a finite domain and Γ \Gamma Γ a constraint language that expresses all soft lists. Then, Γ \Gamma Γ expresses all finite-valued unary cost functions on all subsets of D D D .
Proof. Let B ⊆ D B \subseteq D B ⊆ D and u : B → Q ≥ 0 u:B\to\mathbb{Q}_{\ge0} u : B → Q ≥ 0 be an arbitrary function. If ∣ D ∣ ≤ 1 |D|\le1 ∣ D ∣ ≤ 1 , the function h ( d ) = 0 h(d)=0 h ( d ) = 0 suffices since it is the same as u u u up to a constant.
So, assume ∣ D ∣ ≥ 2 |D|\ge2 ∣ D ∣ ≥ 2 . For each d ∈ B d \in B d ∈ B , let h d ∈ pow ( Γ ) h_d \in\operatorname{pow}(\Gamma) h d ∈ pow ( Γ ) be the soft list on D ∖ { d } D\setminus\{d\} D ∖ { d } , so h d ( d ) = 1 h_d(d)=1 h d ( d ) = 1 and h d ( x ) = 0 h_d(x)=0 h d ( x ) = 0 for x ≠ d x\ne d x = d . Define
h ( x ) = ∑ d ∈ B u ( d ) h d ( x ) , h(x)=\sum_{d\in B}u(d)h_d(x), h ( x ) = d ∈ B ∑ u ( d ) h d ( x ) ,
omitting terms with u ( d ) = 0 u(d)=0 u ( d ) = 0 in the sum. Then h h h is a finite-valued nonnegative cost function expressing u u u on B B B .
:::
We now use the work of Thapper and Živný [79 ] to establish that the problem we consider is polynomial-time solvable, or that Γ \Gamma Γ expresses a finite-valued reversing move. The following is a consequence of results in [79 ] , using the assumption that Γ \Gamma Γ expresses all soft lists.
Theorem 5.8 (Follows from [79 Lemma 2.10, Theorem A.1 and Lemma 2.4] ). Let D D D be a fixed finite domain and Γ \Gamma Γ be a finite-valued constraint language over D D D expressing all soft lists. The problem VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) can be solved in polynomial time, or there exist two distinct domain elements d 1 , d 2 ∈ D d_1,d_2 \in D d 1 , d 2 ∈ D such that Γ \Gamma Γ expresses a finite-valued reversing move on { d 1 , d 2 } \{d_1,d_2\} { d 1 , d 2 } .
Note that Theorem 5.8 above is indeed unconditionally true. However, if P = N P P = NP P = N P , then VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) is always polynomial-time solvable and the first disjunct is always true. Later, we will show that if Γ \Gamma Γ expresses a finite-valued reversing move on a pair of domain elements, then we can express virtually all cost functions.
Lemma 5.9. Let D D D be a finite domain and Γ \Gamma Γ a finite-valued constraint language over D D D expressing all soft lists. Let D ′ ⊆ D D' \subseteq D D ′ ⊆ D contain exactly one element of each equivalence class of ≡ Γ \equiv_\Gamma ≡ Γ . Assume that Γ \Gamma Γ expresses a finite-valued reversing move on { a , b } \{a,b\} { a , b } for some distinct a , b ∈ D a,b \in D a , b ∈ D . Then ∣ D ′ ∣ ≥ 2 |D'| \ge2 ∣ D ′ ∣ ≥ 2 and Γ \Gamma Γ expresses all finite-valued cost functions on D ′ D' D ′ .
We defer the proof of Lemma 5.9 until the end of this subsection. We are now ready to show that, assuming c Γ ≥ 2 c_\Gamma\ge2 c Γ ≥ 2 , we have c Γ = q Γ c_\Gamma= q_\Gamma c Γ = q Γ . A reversing move can only join different additive-equivalence classes, while Lemma 5.9 supplies a single binary cost function with the required values on a set of representatives.
Lemma 2.2. Let D D D be a fixed finite domain, and Γ \Gamma Γ be a finite-valued soft-list language over D D D . If c Γ ≥ 2 c_\Gamma\ge2 c Γ ≥ 2 , then c Γ = q Γ c_\Gamma= q_\Gamma c Γ = q Γ .
Proof. A function witnessing a set in Definition 5.5 is a reversing move on every two-element subset of that set. Since Γ \Gamma Γ expresses all soft lists, neither of two distinct elements dominates the other. Hence a reversing move on { a , b } \{a,b\} { a , b } witnesses interaction between a a a and b b b . It follows directly from the definitions (and also from Lemma 5.11 given later) that these elements cannot be additively equivalent. Thus any subset counted by c Γ c_\Gamma c Γ contains at most one element from each additive-equivalence class, giving c Γ ≤ q Γ c_\Gamma\le q_\Gamma c Γ ≤ q Γ .
Let D ′ ⊆ D D' \subseteq D D ′ ⊆ D contain exactly one element of each additive-equivalence class. Since c Γ ≥ 2 c_\Gamma\ge2 c Γ ≥ 2 and Γ \Gamma Γ is finite-valued, Γ \Gamma Γ expresses a finite-valued reversing move on some pair of distinct elements. By Lemma 5.9, Γ \Gamma Γ therefore expresses all finite-valued cost functions on D ′ D' D ′ , including one of the required form (where we use soft lists to ensure the values outside D ′ D' D ′ are penalized sufficiently), and c Γ ≥ q Γ c_\Gamma\ge q_\Gamma c Γ ≥ q Γ .
:::
Note that by Theorem 5.8 the problem is polynomial-time solvable when c Γ = 1 c_\Gamma= 1 c Γ = 1 . Hence, c Γ c_\Gamma c Γ and q Γ q_\Gamma q Γ coincide for all cases that are not polynomial-time solvable, and our lower bound follows from Lemma 5.6 .
Expressing cost functions. It remains to prove Lemma 5.9, that is, that we can express all finite-valued cost functions on the remaining domain. First, we can observe that if all soft lists are available no element dominates another.
Observation 5.10. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D expressing all soft lists. No element of D D D dominates a distinct element.
Domination consequently causes no additional restriction in the soft-list setting. Now, we tie the notion of interaction to additive equivalence.
Lemma 5.11. Let D D D be a finite domain and Γ \Gamma Γ be a finite-valued constraint language over D D D expressing a restriction to { d } \{d\} { d } for each d ∈ D d \in D d ∈ D . Then, two distinct elements d 1 , d 2 ∈ D d_1,d_2 \in D d 1 , d 2 ∈ D are additively equivalent if and only if they do not interact.
Proof. First, assume that d 1 d_1 d 1 and d 2 d_2 d 2 are not additively equivalent. Then, there is a cost function f ∈ Γ f \in\Gamma f ∈ Γ of arity a a a , a position i ∈ { 1 , … , a } i \in\{1,\ldots,a\} i ∈ { 1 , … , a } , and domain elements w 1 , … , w a − 1 , z 1 , … , z a − 1 w_1,\ldots,w_{a-1},z_1,\ldots,z_{a-1} w 1 , … , w a − 1 , z 1 , … , z a − 1 such that
f ( w 1 , … , w i − 1 , d 1 , w i , … , w a − 1 ) − f ( w 1 , … , w i − 1 , d 2 , w i , … , w a − 1 ) ≠ f ( z 1 , … , z i − 1 , d 1 , z i , … , z a − 1 ) − f ( z 1 , … , z i − 1 , d 2 , z i , … , z a − 1 ) . f(w_1,\ldots,w_{i-1},d_1,w_i,\ldots,w_{a-1})-f(w_1,\ldots,w_{i-1},d_2,w_i,\ldots,w_{a-1})
\ne f(z_1,\ldots,z_{i-1},d_1,z_i,\ldots,z_{a-1})-f(z_1,\ldots,z_{i-1},d_2,z_i,\ldots,z_{a-1}). f ( w 1 , … , w i − 1 , d 1 , w i , … , w a − 1 ) − f ( w 1 , … , w i − 1 , d 2 , w i , … , w a − 1 ) = f ( z 1 , … , z i − 1 , d 1 , z i , … , z a − 1 ) − f ( z 1 , … , z i − 1 , d 2 , z i , … , z a − 1 ) .
Consider the sequence of replacements, where the entries of the first tuple w 1 , … , w a − 1 w_1,\ldots,w_{a-1} w 1 , … , w a − 1 are changed to the entries of the second tuple z 1 , … , z a − 1 z_1,\ldots,z_{a-1} z 1 , … , z a − 1 one position at a time. Since the differences at the first and last tuples are different, at least one step changes this difference. The tuples before and after this step differ in only a single element. Hence, we can assume that w j = z j w_j = z_j w j = z j , apart from a single index j j j in which they differ.
Let g ( x , y ) g(x,y) g ( x , y ) be obtained from f f f by putting x x x in position i i i , putting y y y in the position corresponding to w j w_j w j and z j z_j z j , and fixing every remaining argument to its common value in the two tuples. Then,
g ( d 1 , w j ) − g ( d 2 , w j ) ≠ g ( d 1 , z j ) − g ( d 2 , z j ) . (1) g(d_1,w_j)-g(d_2,w_j) \ne g(d_1,z_j)-g(d_2,z_j). \tag*{(1)} g ( d 1 , w j ) − g ( d 2 , w j ) = g ( d 1 , z j ) − g ( d 2 , z j ) . (1)
To express g g g , add for each fixed position an auxiliary variable with a restriction to its common value in both tuples, weighted so that its penalty for any other value exceeds max f − min f \max f-\min f max f − min f . Minimizing over the auxiliary variables then gives g g g plus a constant, so g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) .
Due to the restrictions that Γ \Gamma Γ expresses, neither of d 1 , d 2 d_1,d_2 d 1 , d 2 dominates the other. Thus, g g g witnesses the interaction of d 1 d_1 d 1 and d 2 d_2 d 2 .
For the other direction, assume that d 1 d_1 d 1 and d 2 d_2 d 2 are additively equivalent, and consider any finite-valued binary cost function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) . Take a gadget expressing g g g , with distinguished variables x x x and y y y . For any fixed assignment to y y y and the auxiliary variables, changing x x x from d 2 d_2 d 2 to d 1 d_1 d 1 changes the total cost by the same constant Δ x \Delta_x Δ x . This constant is obtained by summing the weighted witnessing constants c f , i d 1 , d 2 c_{f,i}^{d_1,d_2} c f , i d 1 , d 2 over all occurrences of x x x in the gadget’s constraints, as in the proof of Lemma 5.3 . In particular, each constant used in the sum does not depend on the assignment to y y y or the auxiliary variables. Minimizing over the auxiliary variables therefore preserves this difference, and any additive constant in the expression for g g g cancels. Hence, for every d ′ ∈ D d' \in D d ′ ∈ D , we have
g ( d 1 , d ′ ) − g ( d 2 , d ′ ) = Δ x . g(d_1,d')-g(d_2,d')=\Delta_x. g ( d 1 , d ′ ) − g ( d 2 , d ′ ) = Δ x .
No such g g g can witness an interaction, so d 1 d_1 d 1 and d 2 d_2 d 2 do not interact.
We now show that essentially all moves exist.
Lemma 2.7. Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D that expresses all soft lists. For any interacting pairs { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } , there is a finite-valued move { a , b } ⇝ { c , d } \{a,b\}\rightsquigarrow\{c,d\} { a , b } ⇝ { c , d } .
Proof. Let a ′ , b ′ a',b' a ′ , b ′ witness the interaction of a , b a,b a , b , and let c ′ , d ′ c',d' c ′ , d ′ witness the interaction of c , d c,d c , d . Let f , g ∈ pow ( Γ ) f,g \in\operatorname{pow}(\Gamma) f , g ∈ pow ( Γ ) be finite-valued binary cost functions witnessing these two interactions, respectively. Thus, Lemma 4.6 gives { a , b } ⇝ { a ′ , b ′ } \{a,b\}\rightsquigarrow\{a',b'\} { a , b } ⇝ { a ′ , b ′ } and { c , d } ⇝ { c ′ , d ′ } \{c,d\}\rightsquigarrow\{c',d'\} { c , d } ⇝ { c ′ , d ′ } . For each x ∈ D x \in D x ∈ D , define
Δ 1 ( x ) = f ( x , a ′ ) − f ( x , b ′ ) , Δ 2 ( x ) = g ( x , c ′ ) − g ( x , d ′ ) . \Delta_1(x)=f(x,a')-f(x,b'),\qquad\Delta_2(x)=g(x,c')-g(x,d'). Δ 1 ( x ) = f ( x , a ′ ) − f ( x , b ′ ) , Δ 2 ( x ) = g ( x , c ′ ) − g ( x , d ′ ) .
By the choice of the witnesses, we have Δ 1 ( a ) ≠ Δ 1 ( b ) \Delta_1(a)\ne\Delta_1(b) Δ 1 ( a ) = Δ 1 ( b ) and Δ 2 ( c ) ≠ Δ 2 ( d ) \Delta_2(c)\ne\Delta_2(d) Δ 2 ( c ) = Δ 2 ( d ) .
If Δ 2 ( a ) ≠ Δ 2 ( b ) \Delta_2(a)\ne\Delta_2(b) Δ 2 ( a ) = Δ 2 ( b ) , then c ′ , d ′ c',d' c ′ , d ′ also witness the interaction of a , b a,b a , b . Hence, { a , b } ⇝ { c ′ , d ′ } ⇝ { c , d } \{a,b\}\rightsquigarrow\{c',d'\}\rightsquigarrow\{c,d\} { a , b } ⇝ { c ′ , d ′ } ⇝ { c , d } , which gives the desired move by Lemma 4.3 .
Otherwise, Δ 2 ( a ) = Δ 2 ( b ) \Delta_2(a)=\Delta_2(b) Δ 2 ( a ) = Δ 2 ( b ) . Since Δ 2 ( c ) ≠ Δ 2 ( d ) \Delta_2(c)\ne\Delta_2(d) Δ 2 ( c ) = Δ 2 ( d ) , we can choose e ∈ { c , d } e \in\{c,d\} e ∈ { c , d } such that Δ 2 ( e ) ≠ Δ 2 ( a ) \Delta_2(e)\ne\Delta_2(a) Δ 2 ( e ) = Δ 2 ( a ) . Since Δ 1 ( a ) ≠ Δ 1 ( b ) \Delta_1(a)\ne\Delta_1(b) Δ 1 ( a ) = Δ 1 ( b ) , we can also choose r ∈ { a , b } r \in\{a,b\} r ∈ { a , b } such that Δ 1 ( r ) ≠ Δ 1 ( e ) \Delta_1(r)\ne\Delta_1(e) Δ 1 ( r ) = Δ 1 ( e ) . We then have
Δ 1 ( r ) ≠ Δ 1 ( e ) , Δ 2 ( r ) = Δ 2 ( a ) ≠ Δ 2 ( e ) . \Delta_1(r)\ne\Delta_1(e),\qquad\Delta_2(r)=\Delta_2(a)\ne\Delta_2(e). Δ 1 ( r ) = Δ 1 ( e ) , Δ 2 ( r ) = Δ 2 ( a ) = Δ 2 ( e ) .
These inequalities imply r ≠ e r\ne e r = e , and neither r r r nor e e e dominates the other by assumption. Thus, a ′ , b ′ a',b' a ′ , b ′ and c ′ , d ′ c',d' c ′ , d ′ both witness the interaction of r , e r,e r , e . Applying Lemma 4.6 and transposing moves where needed gives
{ a , b } ⇝ { a ′ , b ′ } ⇝ { r , e } ⇝ { c ′ , d ′ } ⇝ { c , d } . \{a,b\}\rightsquigarrow\{a',b'\}\rightsquigarrow\{r,e\}\rightsquigarrow\{c',d'\}\rightsquigarrow\{c,d\}. { a , b } ⇝ { a ′ , b ′ } ⇝ { r , e } ⇝ { c ′ , d ′ } ⇝ { c , d } .
The moves compose and we have { a , b } ⇝ { c , d } \{a,b\}\rightsquigarrow\{c,d\} { a , b } ⇝ { c , d } . The moves obtained from Lemma 4.6 are finite-valued, and their compositions are also finite-valued by Lemma 4.3 .
We can now finish the deferred proof.
Lemma 5.9. Let D D D be a finite domain and Γ \Gamma Γ a finite-valued constraint language over D D D expressing all soft lists. Let D ′ ⊆ D D' \subseteq D D ′ ⊆ D contain exactly one element of each equivalence class of ≡ Γ \equiv_\Gamma ≡ Γ . Assume that Γ \Gamma Γ expresses a finite-valued reversing move on { a , b } \{a,b\} { a , b } for some distinct a , b ∈ D a,b \in D a , b ∈ D . Then ∣ D ′ ∣ ≥ 2 |D'| \ge2 ∣ D ′ ∣ ≥ 2 and Γ \Gamma Γ expresses all finite-valued cost functions on D ′ D' D ′ .
Proof. Let g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) be a finite-valued reversing move on P = { a , b } P = \{a,b\} P = { a , b } . It satisfies g ( a , a ) + g ( b , b ) > g ( a , b ) + g ( b , a ) g(a,a) + g(b,b) > g(a,b) + g(b,a) g ( a , a ) + g ( b , b ) > g ( a , b ) + g ( b , a ) , and neither element dominates the other by Observation 5.10. Thus P P P is interacting. By Lemma 5.11, its elements are not additively equivalent, so ∣ D ′ ∣ ≥ 2 |D'| \ge2 ∣ D ′ ∣ ≥ 2 . Any two distinct elements of D ′ D' D ′ belong to different equivalence classes, so D ′ D' D ′ is pairwise interacting by the same lemma.
By Lemma 5.7, soft lists give all finite-valued unary cost functions on P P P and on D ′ D' D ′ , as well as a restriction to P P P . The reversing move g g g and the restriction to P P P let us apply Lemma 4.7 to express all finite-valued cost functions on P P P . Lemma 2.7 gives a finite-valued move from every pair of distinct elements in D ′ D' D ′ to P P P . We can therefore apply Lemma 4.8 to express all finite-valued cost functions on D ′ D' D ′ .
VCSP over Finite-Valued Hard-List Languages
We now consider finite-valued hard-list languages, which need not contain all soft lists. For this, we recall the formal definitions of hard lists and finite-valued hard-list languages.
Definition 3.3 (Hard lists). Let D D D be a finite domain. A hard list on D ′ ⊆ D D' \subseteq D D ′ ⊆ D is the cost function f f f defined by f ( d ) = 0 f(d) = 0 f ( d ) = 0 if d ∈ D ′ d \in D' d ∈ D ′ and f ( d ) = ∞ f(d) = \infty f ( d ) = ∞ if d ∉ D ′ d \notin D' d ∈ / D ′ . A constraint language Γ \Gamma Γ over D D D contains all hard lists if, for all D ′ ⊆ D D' \subseteq D D ′ ⊆ D , the language Γ \Gamma Γ contains the hard list on D ′ D' D ′ .
Definition 3.4 (Finite-valued hard-list language). Let D D D be a finite domain and let H D \mathcal{H}_D H D be the set of all hard lists on D D D . A constraint language Γ \Gamma Γ over D D D is a finite-valued hard-list language if Γ = Φ ∪ H D \Gamma= \Phi\cup\mathcal{H}_D Γ = Φ ∪ H D for some finite-valued constraint language Φ \Phi Φ over D D D . Equivalently, Γ \Gamma Γ contains all hard lists and every cost function in Γ ∖ H D \Gamma\setminus\mathcal{H}_D Γ ∖ H D is finite-valued. In an instance over Γ \Gamma Γ , a non-hard-list constraint is a constraint whose cost function belongs to Γ ∖ H D \Gamma\setminus\mathcal{H}_D Γ ∖ H D .
Our algorithm and lower bound will again be tied to properties of the available domain elements. Unlike in the soft-list setting, distinct available elements may dominate one another. An expressive set combines interaction with the ability to express soft lists.
Definition 2.11 (Expressive set). Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . A set D ′ ⊆ D D' \subseteq D D ′ ⊆ D is expressive if
(1) D ′ D' D ′ is pairwise interacting, and
(2) Γ \Gamma Γ expresses all soft lists on D ′ D' D ′ .
If Γ \Gamma Γ expresses all soft lists, condition (2) is automatic, as in Section 5. Moreover, condition (2) holds if and only if Γ \Gamma Γ expresses all finite-valued unary cost functions on D ′ D' D ′ . Indeed, for every S ⊆ D ′ S \subseteq D' S ⊆ D ′ , the restriction of the soft list h S h_S h S to D ′ D' D ′ is such a function. Conversely, if ∣ D ′ ∣ ≥ 2 |D'| \ge2 ∣ D ′ ∣ ≥ 2 , then for each d ∈ D ′ d \in D' d ∈ D ′ , condition (2) applied to the soft list on D ′ ∖ { d } D' \setminus\{d\} D ′ ∖ { d } gives a finite-valued unary g d ∈ pow ( Γ ) g_d \in\operatorname{pow}(\Gamma) g d ∈ pow ( Γ ) and c d ∈ Q c_d \in\mathbb{Q} c d ∈ Q with g d = h D ′ ∖ { d } + c d g_d = h_{D' \setminus\{d\}} + c_d g d = h D ′ ∖ { d } + c d on D ′ D' D ′ . For every u : D ′ → Q ≥ 0 u: D' \to\mathbb{Q}_{\ge0} u : D ′ → Q ≥ 0 , the function ∑ d ∈ D ′ u ( d ) g d \sum_{d \in D'} u(d)g_d ∑ d ∈ D ′ u ( d ) g d then equals u + ∑ d ∈ D ′ u ( d ) c d u + \sum_{d \in D'} u(d)c_d u + ∑ d ∈ D ′ u ( d ) c d on D ′ D' D ′ , as in the proof of Lemma 5.7. If ∣ D ′ ∣ = 1 |D'| = 1 ∣ D ′ ∣ = 1 , every unary function on D ′ D' D ′ is constant there, and condition (2) applied to the soft list on D ′ D' D ′ gives a finite-valued unary function in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) that is constant on D ′ D' D ′ .
The Algorithm
First, we show that the running time of solving VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) on graphs of bounded treewidth can be tied to the size of expressive sets. We preprocess our instance using the steps described next.
Preprocessing and Block Decomposition.
We begin with simple reductions that shrink the available sets of the variables, and then split the instance into independent subinstances according to the blocks of the move graph.
Removing dominated elements. First, we give a simple preprocessing algorithm that deletes dominated elements from the available sets of variables. The upcoming deletion rules in Lemmas 6.1 and 6.3 are special cases of soft neighborhood substitution [24 , 4 , 64 , 29 ] : for a variable v v v of an instance, a domain element a a a can be discarded when there is another available element b b b that is at least as good, regardless of the assignment to the neighboring variables.
Lemma 6.1. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Given an instance I I I of VCSP(Γ \Gamma Γ ), one can in polynomial time add hard-list constraints to obtain an instance I ′ I' I ′ of VCSP(Γ \Gamma Γ ) with the same optimum cost and the same primal graph such that, for each variable, no available element is dominated by a distinct available element.
Proof. Let a , b a,b a , b be distinct available elements at a variable v v v , with a a a dominating b b b . We show that changing the value of v v v from b b b to a a a never increases the cost. The hard lists at v v v allow both a a a and b b b . Consider any other constraint at v v v ; its cost function f f f is finite-valued. Let i i i be a position of f f f . Suppose that, for some values at the other positions, f f f is more expensive with a a a at position i i i than with b b b . Fixing the other positions to these values by singleton hard lists expresses a finite-valued unary function in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) that is cheaper at b b b than at a a a , contradicting that a a a dominates b b b . Hence, for all values at the other positions, replacing b b b by a a a at position i i i does not increase the cost of f f f . Applying this to the occurrences of v v v one at a time proves the claim.
Hence, adding a hard list at v v v that forbids b b b does not change the optimum cost. Repeating this while some variable has an available element dominated by a distinct available one removes one element each time, so it stops after at most ( ∣ D ∣ − 1 ) ⋅ ∣ V ∣ (|D|-1)\cdot|V| ( ∣ D ∣ − 1 ) ⋅ ∣ V ∣ steps.
Reduction to binary functions. We now introduce a useful lemma whose point is reducing properties of higher-arity functions to binary functions. For a partition S , T S,T S , T of [ m ] [m] [ m ] and x ˉ , y ˉ ∈ D m \bar{x},\bar{y}\in D^m x ˉ , y ˉ ∈ D m , we write x ˉ S ⋅ y ˉ T \bar{x}_S\cdot\bar{y}_T x ˉ S ⋅ y ˉ T for the tuple that agrees with x ˉ \bar{x} x ˉ on S S S and with y ˉ \bar{y} y ˉ on T T T . For J ⊆ [ m ] J\subseteq[m] J ⊆ [ m ] and z ˉ ∈ D m \bar{z}\in D^m z ˉ ∈ D m , we write z ˉ J \bar{z}_J z ˉ J for the subtuple of z ˉ \bar{z} z ˉ at the indices in J J J , in increasing order.
Lemma 6.2. Let D D D be a finite domain, Γ \Gamma Γ a finite-valued hard-list language over D D D , and g ∈ pow ( Γ ) g\in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) a finite-valued cost function of arity m m m . Let S , T S,T S , T be a partition of [ m ] [m] [ m ] and x ˉ , y ˉ ∈ D m \bar{x},\bar{y}\in D^m x ˉ , y ˉ ∈ D m with
g ( x ˉ ) + g ( y ˉ ) < g ( x ˉ S ⋅ y ˉ T ) + g ( y ˉ S ⋅ x ˉ T ) . g(\bar{x})+g(\bar{y})<g(\bar{x}_S\cdot\bar{y}_T)+g(\bar{y}_S\cdot\bar{x}_T). g ( x ˉ ) + g ( y ˉ ) < g ( x ˉ S ⋅ y ˉ T ) + g ( y ˉ S ⋅ x ˉ T ) . Then there are i ∈ S i\in S i ∈ S and j ∈ T j\in T j ∈ T with x i ≠ y i x_i\ne y_i x i = y i and x j ≠ y j x_j\ne y_j x j = y j , and a finite-valued binary h ∈ pow ( Γ ) h\in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) such that
h ( x i , x j ) + h ( y i , y j ) < h ( x i , y j ) + h ( y i , x j ) . h(x_i,x_j)+h(y_i,y_j)<h(x_i,y_j)+h(y_i,x_j). h ( x i , x j ) + h ( y i , y j ) < h ( x i , y j ) + h ( y i , x j ) . The same holds with both inequalities reversed.
Proof. The first claim is [42 Lemma 12] . Since g g g is finite-valued, the proof there only fixes coordinates to entries of x ˉ \bar{x} x ˉ or y ˉ \bar{y} y ˉ . We express this using singleton hard lists, so the binary function it produces is a finite-valued h ∈ pow ( Γ ) h\in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) . The strict inequality forces x i ≠ y i x_i\ne y_i x i = y i and x j ≠ y j x_j\ne y_j x j = y j . For the reversed inequalities, apply the first claim to x ˉ S ⋅ y ˉ T \bar{x}_S\cdot\bar{y}_T x ˉ S ⋅ y ˉ T and y ˉ S ⋅ x ˉ T \bar{y}_S\cdot\bar{x}_T y ˉ S ⋅ x ˉ T .
Ensuring interaction. Next, we extend our preprocessing to make sure the available sets are pairwise interacting. We reuse the cost comparison argument for additive equivalence, applied to the currently available assignments.
Lemma 6.3. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Given an instance I I I of VCSP(Γ \Gamma Γ ) in which every variable has a nonempty set of available elements, one can in polynomial time add hard-list constraints to obtain an instance I ′ I' I ′ with the same optimum cost and primal graph such that every variable has a nonempty, pairwise interacting set of available elements.
Proof. First apply Lemma 6.1 to remove elements that are dominated by another available element from each available set. At a variable v v v , identify repeated occurrences of each variable in every incident non-hard-list constraint C C C , to obtain a finite-valued cost function g C ( x ˉ , y ˉ ) ∈ pow ( Γ ) g_C(\bar{x},\bar{y})\in\operatorname{pow}(\Gamma) g C ( x ˉ , y ˉ ) ∈ pow ( Γ ) with x x x representing v v v . Test whether distinct available elements a , b a,b a , b make
g C ( a , y ˉ ) − g C ( b , y ˉ ) g_C(a,\bar{y})-g_C(b,\bar{y}) g C ( a , y ˉ ) − g C ( b , y ˉ )
constant over all available assignments y ˉ \bar{y} y ˉ , for each such constraint. If this is indeed the case, like in the cost comparison in the proof of Lemma 5.3, summing these constants with the constraint weights determines whether assigning a a a or b b b is more expensive, and this is independent of the assignment to the other variables. Retain the cheaper choice and forbid the other by a hard list. This preserves the optimum, since both choices were available. Repeat this operation while such a deletion is possible.
To show that the remaining available sets are pairwise interacting, suppose that distinct available elements a , b a,b a , b at v v v do not interact. If g C ( a , y ˉ ) − g C ( b , y ˉ ) g_C(a,\bar{y})-g_C(b,\bar{y}) g C ( a , y ˉ ) − g C ( b , y ˉ ) were nonconstant for some C C C , that is, different for two available tuples y ˉ , y ˉ ′ \bar{y},\bar{y}' y ˉ , y ˉ ′ , then Lemma 6.2, applied to ( a , y ˉ ) (a,\bar{y}) ( a , y ˉ ) and ( b , y ˉ ′ ) (b,\bar{y}') ( b , y ˉ ′ ) with S S S consisting of the first position, would give a finite-valued binary function q ∈ pow ( Γ ) q \in\operatorname{pow}(\Gamma) q ∈ pow ( Γ ) and distinct available values c , d c,d c , d at another variable with
q ( a , c ) − q ( b , c ) ≠ q ( a , d ) − q ( b , d ) . q(a,c)-q(b,c) \ne q(a,d)-q(b,d). q ( a , c ) − q ( b , c ) = q ( a , d ) − q ( b , d ) .
The initial preprocessing using Lemma 6.1 excludes domination on both available pairs, so q q q would witness interaction of a , b a,b a , b . Hence all these differences are constant, and the preprocessing would have removed a a a or b b b from L v L_v L v .
There are at most ∣ D ∣ − 1 |D|-1 ∣ D ∣ − 1 deletions per variable, and Γ , D \Gamma,D Γ , D are fixed and finite. Hence the procedure runs in polynomial time. As only unary constraints are added the primal graph is unchanged.
The move graph. By Lemma 4.6, every interaction witness yields a finite-valued move to one ordering of its witness pair. We capture these moves in a graph on ordered pairs that we call the move graph .
Definition 6.4 (Move graph). Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . The move graph G Γ G_\Gamma G Γ (of Γ \Gamma Γ ) has a vertex ( a , b ) (a,b) ( a , b ) for each ordering of an interacting pair { a , b } \{a,b\} { a , b } . There is an edge between ( a , b ) (a,b) ( a , b ) and ( c , d ) (c,d) ( c , d ) if a finite-valued move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) belongs to pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) . Loops are allowed.
Swapping the two arguments of a finite-valued move gives, by Lemma 4.3, a finite-valued move in the reverse direction, so the move graph is undirected. The second part of Lemma 4.3 lets us compose moves along walks.
Observation 6.5. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . If ( a , b ) (a,b) ( a , b ) and ( c , d ) (c,d) ( c , d ) are in the same connected component of the move graph G Γ G_\Gamma G Γ , then there is a finite-valued move from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) .
Proof. Compose the moves along a walk from ( a , b ) (a,b) ( a , b ) to ( c , d ) (c,d) ( c , d ) in G Γ G_\Gamma G Γ , using Lemma 4.3 with the hard list on each intermediate pair as the restriction. If ( a , b ) = ( c , d ) (a,b)=(c,d) ( a , b ) = ( c , d ) , use a walk to a neighbor and back. A neighbor exists because { a , b } \{a,b\} { a , b } is interacting, so Lemma 4.6 gives a finite-valued move from ( a , b ) (a,b) ( a , b ) to an ordering of its witness pair, which is itself interacting. □ \square □
Blocks of the move graph. When ( a , b ) ⇝ ( c , d ) (a,b)\leadsto(c,d) ( a , b ) ⇝ ( c , d ) , we also have ( b , a ) ⇝ ( d , c ) (b,a)\leadsto(d,c) ( b , a ) ⇝ ( d , c ) , witnessed by the same move function (see the discussion in Section 4). Naturally, either ( a , b ) (a,b) ( a , b ) is in the same connected component of the move graph as ( b , a ) (b,a) ( b , a ) , or in a different one. It turns out that this is a very crucial difference. Indeed, a finite-valued reversing move on { a , b } \{a,b\} { a , b } can be expressed only if ( a , b ) (a,b) ( a , b ) and ( b , a ) (b,a) ( b , a ) are in the same connected component.
Consider some connected component C C C of the move graph, and let ( a , b ) (a,b) ( a , b ) be a vertex of the connected component. If ( b , a ) (b,a) ( b , a ) is also part of C C C , then for all vertices ( a ′ , b ′ ) (a',b') ( a ′ , b ′ ) of C C C we have that also ( b ′ , a ′ ) (b',a') ( b ′ , a ′ ) is part of C C C by the preceding note. Otherwise, let C ′ C' C ′ be the connected component of the move graph that contains ( b , a ) (b,a) ( b , a ) . Then, again by the preceding note, we have for all vertices ( a ′ , b ′ ) (a',b') ( a ′ , b ′ ) of C C C that ( b ′ , a ′ ) (b',a') ( b ′ , a ′ ) is part of C ′ C' C ′ . We define blocks of the move graph based on this observation.
For a vertex ( a , b ) (a,b) ( a , b ) of the move graph let ρ ( a , b ) = ( b , a ) \rho(a,b)=(b,a) ρ ( a , b ) = ( b , a ) be the vertex obtained by reversing the pair. Similarly, for a set of vertices S S S of the move graph let ρ ( S ) \rho(S) ρ ( S ) be the set obtained from S S S by applying ρ \rho ρ to each element of S S S .
Definition 6.6 (Blocks of the move graph). Let D D D be a finite domain and Γ \Gamma Γ a constraint language over D D D . Let G Γ G_\Gamma G Γ be the move graph of Γ \Gamma Γ . A block of G Γ G_\Gamma G Γ is a set B = C ∪ ρ ( C ) B=C\cup\rho(C) B = C ∪ ρ ( C ) , where C C C is the vertex set of a connected component of G Γ G_\Gamma G Γ . It is reversing if C = ρ ( C ) C=\rho(C) C = ρ ( C ) and nonreversing otherwise.
In a reversing block, Observation 6.5 gives a finite-valued reversing move on every pair in the block. In a nonreversing block, each component contains exactly one ordering of every unordered pair. Blocks give a natural partition of the vertex set of the move graph, and we can assign unordered pairs to unique blocks.
Definition 6.7 (Blocks of pairs). Let D D D be a finite domain, Γ \Gamma Γ a constraint language over D D D , and G Γ G_\Gamma G Γ the move graph. For a vertex ( a , b ) ∈ V ( G Γ ) (a,b)\in V(G_\Gamma) ( a , b ) ∈ V ( G Γ ) the block of ( a , b ) (a,b) ( a , b ) is the block of the move graph that contains ( a , b ) (a,b) ( a , b ) . For an interacting pair { a , b } \{a,b\} { a , b } the block of { a , b } \{a,b\} { a , b } is the block of ( a , b ) (a,b) ( a , b ) . When B B B is the block of ( a , b ) (a,b) ( a , b ) ({ a , b } \{a,b\} { a , b } ) we also say that ( a , b ) (a,b) ( a , b ) ({ a , b } \{a,b\} { a , b } ) belongs to B B B .
Next, we show that, as for pairs in Definition 6.7 , every pairwise interacting set of at least two elements can be assigned to a unique block.
Lemma 2.10. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Let L ⊆ D L \subseteq D L ⊆ D be pairwise interacting and of size at least 2 2 2 . All pairs of distinct elements of L L L belong to one block of G Γ G_{\Gamma} G Γ .
Proof. The claim holds for ∣ L ∣ = 2 |L|=2 ∣ L ∣ = 2 by the definition of a block. Let a , b , c ∈ L a,b,c\in L a , b , c ∈ L be distinct, and let g g g and { s , t } \{s,t\} { s , t } witness the interaction of a , b a,b a , b (transposing g g g shows that { s , t } \{s,t\} { s , t } is interacting). Writing Δ ( x , y ) = g ( x , s ) − g ( y , s ) − g ( x , t ) + g ( y , t ) \Delta(x,y)=g(x,s)-g(y,s)-g(x,t)+g(y,t) Δ ( x , y ) = g ( x , s ) − g ( y , s ) − g ( x , t ) + g ( y , t ) , we have 0 ≠ Δ ( a , b ) = Δ ( a , c ) + Δ ( c , b ) 0\ne\Delta(a,b)=\Delta(a,c)+\Delta(c,b) 0 = Δ ( a , b ) = Δ ( a , c ) + Δ ( c , b ) . Hence g g g and { s , t } \{s,t\} { s , t } also witness the interaction of a , c a,c a , c or of c , b c,b c , b . By Lemma 4.6, the pair { s , t } \{s,t\} { s , t } lies in the block of { a , b } \{a,b\} { a , b } and in the block of { a , c } \{a,c\} { a , c } or of { c , b } \{c,b\} { c , b } . So each of the three pairs on { a , b , c } \{a,b,c\} { a , b , c } shares its block with another of them, and all three belong to one block. Finally, two disjoint pairs { a , b } \{a,b\} { a , b } and { c , d } \{c,d\} { c , d } in L L L both share a block with { a , c } \{a,c\} { a , c } .
This lemma justifies extending our notion of pairs belonging to a block to sets belonging to a block.
Definition 6.8 (Blocks of sets). Let D D D be a finite domain, Γ \Gamma Γ a constraint language over D D D , G Γ G_{\Gamma} G Γ its move graph, and S S S a pairwise interacting set of elements of D D D . If ∣ S ∣ ≤ 1 |S|\le1 ∣ S ∣ ≤ 1 , then S S S does not belong to a block. If ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2 , let a , b a,b a , b be two distinct elements of S S S ; then S S S belongs to the block of ( a , b ) (a,b) ( a , b ) .
By Lemma 2.10 the block of a set is well-defined and the choice of the elements a , b a,b a , b does not matter. Since Γ \Gamma Γ is fixed, the move graph, its blocks, and the block of every pairwise interacting subset of D D D are fixed finite data that our algorithms may use.
Decomposing instances. The purpose of blocks now is that they give us a clean decomposition of any instance of VCSP( Γ ) (\Gamma) ( Γ ) . Concretely, we can decompose a given instance into multiple instances in which every available set of size at least two belongs to a single block of the move graph.
The preceding preprocessing leaves every available set nonempty and pairwise interacting. We now separate the instance according to the blocks of the move graph.2
Lemma 6.9. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite, finite-valued hard-list language over D D D . Let I I I be an instance of VCSP( Γ ) (\Gamma) ( Γ ) in which every variable has a nonempty, pairwise interacting set of available elements. For each block B B B of the move graph G Γ G_{\Gamma} G Γ , let V B V_B V B be the set of variables of I I I whose available sets belong to B B B .
One can in polynomial time construct a constant c ∈ Q c\in\mathbb{Q} c ∈ Q and, for each block B B B with V B ≠ ∅ V_B\ne\varnothing V B = ∅ , an instance I B I_B I B of VCSP( Γ ) (\Gamma) ( Γ ) such that
Opt ( I ) = c + ∑ B Opt ( I B ) , \operatorname{Opt}(I)=c+\sum_B \operatorname{Opt}(I_B), Opt ( I ) = c + B ∑ Opt ( I B ) ,
where the sum ranges over blocks with V B ≠ ∅ V_B\ne\varnothing V B = ∅ . We call the instances I B I_B I B the block instances of this decomposition. Each variable of I B I_B I B has an available set that either belongs to B B B or has size one. A supplied tree or path decomposition of the primal graph of I I I of width k k k yields decompositions of the same type and width at most k + O ( 1 ) k+O(1) k + O ( 1 ) for all I B I_B I B in polynomial time.
Proof. For each variable v v v of I I I , let L v L_v L v be its available set. We will decompose each non-hard-list constraint C C C into a sum of constraints whose scopes belong only to a single block.
To do this, fix a non-hard-list constraint C C C of the instance. Let v ⃗ C = ( v 1 , … , v m ) \vec v_C=(v_1,\ldots,v_m) v C = ( v 1 , … , v m ) list the distinct variables of its scope in order of first occurrence, and let g C : D m → Q ≥ 0 g_C:D^m\to\mathbb{Q}_{\ge0} g C : D m → Q ≥ 0 be its cost function after identifying repeated variables. Clearly the resulting constraint g C g_C g C is now in poly ( Γ ) \operatorname{poly}(\Gamma) poly ( Γ ) . Write B C = { B ∣ v i ∈ V B for some i ∈ [ m ] } \mathcal{B}_C=\{B\mid v_i\in V_B\text{ for some }i\in[m]\} B C = { B ∣ v i ∈ V B for some i ∈ [ m ]} for the set of blocks the variables in the scope of the constraint belong to, and q C = ∣ B C ∣ q_C=|\mathcal{B}_C| q C = ∣ B C ∣ . Choose an arbitrary “reference” tuple p ⃗ C = ( p 1 , … , p m ) ∈ L v 1 × ⋯ × L v m \vec p_C=(p_1,\ldots,p_m)\in L_{v_1}\times\cdots\times L_{v_m} p C = ( p 1 , … , p m ) ∈ L v 1 × ⋯ × L v m . Such a tuple exists because all available sets are nonempty by assumption. For each B ∈ B C B\in\mathcal{B}_C B ∈ B C , put J C , B = { i ∈ [ m ] ∣ v i ∈ V B } J_{C,B}=\{i\in[m]\mid v_i\in V_B\} J C , B = { i ∈ [ m ] ∣ v i ∈ V B } . That is, the sets J C , B J_{C,B} J C , B partition the indices of variables with available sets of size at least two according to their blocks.
For each block B ∈ B C B\in\mathcal{B}_C B ∈ B C , let g C , B : D ∣ J C , B ∣ → Q ≥ 0 g_{C,B}:D^{|J_{C,B}|}\to\mathbb{Q}_{\ge0} g C , B : D ∣ J C , B ∣ → Q ≥ 0 be obtained from g C g_C g C by fixing every position outside J C , B J_{C,B} J C , B to its value in p ⃗ C \vec p_C p C ; that is, g C , B ( z ⃗ J C , B ) = g C ( z ⃗ J C , B ⋅ ( p ⃗ C ) [ m ] ∖ J C , B ) g_{C,B}(\vec z_{J_{C,B}})=g_C(\vec z_{J_{C,B}}\cdot(\vec p_C)_{[m]\setminus J_{C,B}}) g C , B ( z J C , B ) = g C ( z J C , B ⋅ ( p C ) [ m ] ∖ J C , B ) for z ⃗ ∈ D m \vec z\in D^m z ∈ D m . Set α C = ( 1 − q C ) g C ( p ⃗ C ) \alpha_C=(1-q_C)g_C(\vec p_C) α C = ( 1 − q C ) g C ( p C ) . We show that, for every z ⃗ ∈ L v 1 × ⋯ × L v m \vec z\in L_{v_1}\times\cdots\times L_{v_m} z ∈ L v 1 × ⋯ × L v m ,
g C ( z ⃗ ) = α C + ∑ B ∈ B C g C , B ( z ⃗ J C , B ) . (2) g_C(\vec z)=\alpha_C+\sum_{B\in\mathcal{B}_C}g_{C,B}(\vec z_{J_{C,B}}). \tag*{(2)} g C ( z ) = α C + B ∈ B C ∑ g C , B ( z J C , B ) . (2)
Fix B ∈ B C B \in\mathcal{B}_C B ∈ B C , and let S = J C , B S = J_{C,B} S = J C , B and T = [ m ] ∖ S T = [m] \setminus S T = [ m ] ∖ S . For all x ˉ , y ˉ ∈ L v 1 × ⋯ × L v m \bar{x}, \bar{y} \in L_{v_1} \times\cdots\times L_{v_m} x ˉ , y ˉ ∈ L v 1 × ⋯ × L v m , we have
g C ( x ˉ ) + g C ( y ˉ ) = g C ( x ˉ S ⋅ y ˉ T ) + g C ( y ˉ S ⋅ x ˉ T ) . (3) g_C(\bar{x}) + g_C(\bar{y}) = g_C(\bar{x}_S \cdot\bar{y}_T) + g_C(\bar{y}_S \cdot\bar{x}_T). \tag*{(3)} g C ( x ˉ ) + g C ( y ˉ ) = g C ( x ˉ S ⋅ y ˉ T ) + g C ( y ˉ S ⋅ x ˉ T ) . (3)
Otherwise, Lemma 6.2 gives i ∈ S i \in S i ∈ S , j ∈ T j \in T j ∈ T , and a finite-valued binary h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) with h ( x i , x j ) − h ( y i , x j ) ≠ h ( x i , y j ) − h ( y i , y j ) h(x_i,x_j) - h(y_i,x_j) \ne h(x_i,y_j) - h(y_i,y_j) h ( x i , x j ) − h ( y i , x j ) = h ( x i , y j ) − h ( y i , y j ) . By assumption, neither element of x i , y i x_i,y_i x i , y i and neither element of x j , y j x_j,y_j x j , y j dominates the other. Hence, x i , y i x_i,y_i x i , y i interact, witnessed by h h h and x j , y j x_j,y_j x j , y j (Definition 2.4). By Lemma 4.6, we then have that { x i , y i } \{x_i,y_i\} { x i , y i } belongs to the same block as { x j , y j } \{x_j,y_j\} { x j , y j } , contradicting v i ∈ V B v_i \in V_B v i ∈ V B and v j ∉ V B v_j \notin V_B v j ∈ / V B .
Taking x ˉ = z ˉ \bar{x} = \bar{z} x ˉ = z ˉ and y ˉ = p ˉ C \bar{y} = \bar{p}_C y ˉ = p ˉ C in (2) gives g C ( z ˉ ) = g C , B ( z ˉ S ) + g C ( z ˉ ′ ) − g C ( p ˉ C ) g_C(\bar{z}) = g_{C,B}(\bar{z}_S) + g_C(\bar{z}') - g_C(\bar{p}_C) g C ( z ˉ ) = g C , B ( z ˉ S ) + g C ( z ˉ ′ ) − g C ( p ˉ C ) , where z ˉ ′ = ( p ˉ C ) S ⋅ z ˉ T \bar{z}' = (\bar{p}_C)_S \cdot\bar{z}_T z ˉ ′ = ( p ˉ C ) S ⋅ z ˉ T . Applying this to the blocks of B C \mathcal{B}_C B C one at a time, and noting that z ˉ \bar{z} z ˉ agrees with p ˉ C \bar{p}_C p ˉ C outside the sets J C , B J_{C,B} J C , B , we obtain
g C ( z ˉ ) = g C ( p ˉ C ) + ∑ B ∈ B C ( g C , B ( z ˉ J C , B ) − g C ( p ˉ C ) ) , g_C(\bar{z}) = g_C(\bar{p}_C) + \sum_{B \in\mathcal{B}_C} \left(g_{C,B}(\bar{z}_{J_{C,B}}) - g_C(\bar{p}_C)\right), g C ( z ˉ ) = g C ( p ˉ C ) + B ∈ B C ∑ ( g C , B ( z ˉ J C , B ) − g C ( p ˉ C ) ) ,
which is (2) . This includes the case q C = 0 q_C = 0 q C = 0 .
Perform this construction for every non-hard-list constraint C C C , and let c = ∑ C weight ( C ) α C c = \sum_C \operatorname{weight}(C)\alpha_C c = ∑ C weight ( C ) α C . For each B B B with V B ≠ ∅ V_B \ne\varnothing V B = ∅ , construct an intermediate weighted constraint system J B J_B J B on the variables V B V_B V B , retaining the hard lists of I I I on these variables. For every C C C with B ∈ B C B \in\mathcal{B}_C B ∈ B C , add ( g C , B , v ˉ C , B , weight ( C ) ) (g_{C,B},\bar{v}_{C,B},\operatorname{weight}(C)) ( g C , B , v ˉ C , B , weight ( C )) to J B J_B J B , where v ˉ C , B \bar{v}_{C,B} v ˉ C , B is the subtuple of v ˉ C \bar{v}_C v ˉ C indexed by J C , B J_{C,B} J C , B . For every available assignment π \pi π of I I I , write π B \pi_B π B for its restriction to V B V_B V B . Then, (2) gives
cost I ( π ) = c + ∑ B cost J B ( π B ) . \operatorname{cost}_I(\pi) = c + \sum_B \operatorname{cost}_{J_B}(\pi_B). cost I ( π ) = c + B ∑ cost J B ( π B ) .
Conversely, assignments to the disjoint sets V B V_B V B combine with the unique available values of all other original variables. Taking optimal assignments gives Opt ( I ) = c + ∑ B Opt ( J B ) \operatorname{Opt}(I) = c + \sum_B \operatorname{Opt}(J_B) Opt ( I ) = c + ∑ B Opt ( J B ) .
Every scope of J B J_B J B is contained in an original constraint scope. Intersecting the bags of a supplied tree or path decomposition with V B V_B V B therefore gives a decomposition of J B J_B J B of the same type and no greater width.
To obtain the desired instance, it remains to introduce gadgets for the functions g C , B g_{C,B} g C , B . This is easy to achieve while only increasing the width of the provided decomposition by a constant, because each function g C , B g_{C,B} g C , B is obtained from a function of Γ \Gamma Γ by identifying variables, and fixing variables to domain values using hard lists.
Solving Instances of Nonreversing Blocks
We now explain how instances of nonreversing blocks can be solved in polynomial time. As in [57 Section 5] , a nonreversing block yields a symmetric tournament pair (STP) multimorphism, so the corresponding instances can be solved by the algorithm of Cohen, Cooper, and Jeavons [CCJ08], which relies on a reduction to submodular function minimization.
Lemma 6.10. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite, finite-valued hard-list language over D D D . Let I I I be an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) in which every variable has a nonempty, pairwise interacting set of available elements. If all available sets of size at least two belong to one nonreversing block of G Γ G_\Gamma G Γ , then an optimal assignment of I I I can be found in polynomial time.
Proof. If all available sets are singletons, the claim is trivial. Let B = C ∪ ρ ( C ) B = C \cup\rho(C) B = C ∪ ρ ( C ) be the block. Every finite-valued binary h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) satisfies
h ( a , s ) + h ( b , t ) ≤ h ( a , t ) + h ( b , s ) for all ( a , b ) , ( s , t ) ∈ C . (4) h(a,s) + h(b,t) \le h(a,t) + h(b,s) \qquad\text{for all } (a,b),(s,t) \in C. \tag*{(4)} h ( a , s ) + h ( b , t ) ≤ h ( a , t ) + h ( b , s ) for all ( a , b ) , ( s , t ) ∈ C . (4) Otherwise, Lemma 4.6 gives a move from ( a , b ) ∈ C (a,b) \in C ( a , b ) ∈ C to ( t , s ) ∈ ρ ( C ) (t,s) \in\rho(C) ( t , s ) ∈ ρ ( C ) so C = ρ ( C ) C = \rho(C) C = ρ ( C ) , contradicting that B B B is nonreversing; compare [57 Lemma 5.3] . Every ordering to B B B thus has exactly one ordering in C C C . Hence there is an STP ⟨ ⊓ , ⊔ ⟩ \langle\sqcap,\sqcup\rangle ⟨ ⊓ , ⊔ ⟩ on D D D , that is, a pair of commutative operations with { a ⊓ b , a ⊔ b } = { a , b } \{a \sqcap b,a \sqcup b\} = \{a,b\} { a ⊓ b , a ⊔ b } = { a , b } , such that a ⊓ b = a a \sqcap b = a a ⊓ b = a whenever ( a , b ) ∈ C (a,b) \in C ( a , b ) ∈ C .
Identify repeated variables in each non-hard-list constraint, and replace its finite-valued cost function g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) by the function f f f that agrees with g g g on the product L 1 × ⋯ × L k L_1 \times\cdots\times L_k L 1 × ⋯ × L k of the available sets and is ∞ \infty ∞ elsewhere. This preserves all available assignments and their costs, and only finitely many such f f f arise. Hard lists admit every conservative pair, so by [CCJ08] it suffices to show f ( x ˉ ⊓ y ˉ ) + f ( x ˉ ⊔ y ˉ ) ≤ f ( x ˉ ) + f ( y ˉ ) f(\bar{x} \sqcap\bar{y}) + f(\bar{x} \sqcup\bar{y}) \le f(\bar{x}) + f(\bar{y}) f ( x ˉ ⊓ y ˉ ) + f ( x ˉ ⊔ y ˉ ) ≤ f ( x ˉ ) + f ( y ˉ ) for x ˉ , y ˉ ∈ L 1 × ⋯ × L k \bar{x},\bar{y} \in L_1 \times\cdots\times L_k x ˉ , y ˉ ∈ L 1 × ⋯ × L k , where both ⊓ \sqcap ⊓ and ⊔ \sqcup ⊔ act componentwise on tuples; i.e., x ˉ ⊓ y ˉ = ( x 1 ⊓ y 1 , … , x k ⊓ y k ) \bar{x} \sqcap\bar{y} = (x_1 \sqcap y_1,\ldots,x_k \sqcap y_k) x ˉ ⊓ y ˉ = ( x 1 ⊓ y 1 , … , x k ⊓ y k ) and x ˉ ⊔ y ˉ = ( x 1 ⊔ y 1 , … , x k ⊔ y k ) \bar{x} \sqcup\bar{y} = (x_1 \sqcup y_1,\ldots,x_k \sqcup y_k) x ˉ ⊔ y ˉ = ( x 1 ⊔ y 1 , … , x k ⊔ y k ) , where x ˉ = ( x 1 , … , x k ) \bar{x} = (x_1,\ldots,x_k) x ˉ = ( x 1 , … , x k ) and y ˉ = ( y 1 , … , y k ) \bar{y} = (y_1,\ldots,y_k) y ˉ = ( y 1 , … , y k ) .
Let T = { j : x j ≠ y j , x j ⊓ y j = y j } T=\{j:x_j\ne y_j,\ x_j\sqcap y_j=y_j\} T = { j : x j = y j , x j ⊓ y j = y j } and S = [ k ] ∖ T S=[k]\setminus T S = [ k ] ∖ T , so that x ˉ ⊓ y ˉ = x ˉ S ⋅ y ˉ T \bar{x}\sqcap\bar{y}=\bar{x}_S\cdot\bar{y}_T x ˉ ⊓ y ˉ = x ˉ S ⋅ y ˉ T and x ˉ ⊔ y ˉ = y ˉ S ⋅ x ˉ T \bar{x}\sqcup\bar{y}=\bar{y}_S\cdot\bar{x}_T x ˉ ⊔ y ˉ = y ˉ S ⋅ x ˉ T . If the inequality failed, Lemma 6.2 , applied to g g g , which agrees with f f f on these four tuples, would give i ∈ S i\in S i ∈ S and j ∈ T j\in T j ∈ T with x i ≠ y i x_i\ne y_i x i = y i and x j ≠ y j x_j\ne y_j x j = y j , and a finite-valued binary h ∈ pow ( Γ ) h\in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) with h ( x i , y j ) + h ( y i , x j ) > h ( x i , x j ) + h ( y i , y j ) h(x_i,y_j)+h(y_i,x_j)>h(x_i,x_j)+h(y_i,y_j) h ( x i , y j ) + h ( y i , x j ) > h ( x i , x j ) + h ( y i , y j ) . So L i L_i L i and L j L_j L j have size at least two, and the pairs { x i , y i } \{x_i,y_i\} { x i , y i } and { x j , y j } \{x_j,y_j\} { x j , y j } belong to B B B (Definition 6.8 ). The choice of S S S and T T T now gives ( x i , y i ) , ( y j , x j ) ∈ C (x_i,y_i),(y_j,x_j)\in C ( x i , y i ) , ( y j , x j ) ∈ C , contradicting (3).
Together with Lemma 6.9 , this lets us compute the contribution of every nonreversing block to the optimum in polynomial time.
Expressing Cost Functions on Reversing Blocks
Before proceeding with our approach for reversing blocks, we elaborate on how reversing blocks help us to express cost functions, and establish an alternative characterization of c Γ c_\Gamma c Γ revolving around expressive sets. First, we establish that we can express cost functions on certain set products, assuming that we can express finite-valued unary cost functions.
Corollary 6.11. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Let B B B be a reversing block of G Γ G_\Gamma G Γ , let r ≥ 1 r\ge1 r ≥ 1 , and let S 1 , … , S r ⊆ D S_1,\ldots,S_r\subseteq D S 1 , … , S r ⊆ D be nonempty subsets. Suppose that every S i S_i S i of size at least two is pairwise interacting and belongs to B B B , and that Γ \Gamma Γ expresses all finite-valued unary cost functions on each S i S_i S i . For every f : S 1 × ⋯ × S r → Q ≥ 0 f:S_1\times\cdots\times S_r\to\mathbb{Q}_{\ge0} f : S 1 × ⋯ × S r → Q ≥ 0 , there are a finite-valued g ∈ pow ( Γ ) g\in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c\in\mathbb{Q} c ∈ Q with g = f + c g=f+c g = f + c on S 1 × ⋯ × S r S_1\times\cdots\times S_r S 1 × ⋯ × S r .
Proof. Fix an interacting pair P = { p , q } P=\{p,q\} P = { p , q } in B B B . Neither p p p nor q q q dominates the other, so Lemma 4.5 shows that Γ \Gamma Γ expresses all finite-valued unary cost functions on P P P .
Since B B B is reversing, Observation 6.5 gives a finite-valued reversing move on P P P . The hard list on P P P is zero on P P P and infinite outside it. We can therefore apply Lemma 4.7 to express all finite-valued cost functions on P P P .
Every pair of distinct elements in any set S i S_i S i belongs to B B B , so a walk in this block gives a finite-valued move from that pair to P P P by Observation 6.5 . Together with the assumed unary expressibility on each S i S_i S i , these moves and the hard list on P P P satisfy the hypotheses of Lemma 4.8 , which proves the claim. □
This allows us to characterize the value c Γ c_\Gamma c Γ in terms of the size of expressive sets belonging to reversing blocks.
Lemma 2.12. Let D D D be a finite domain, and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Then c Γ c_\Gamma c Γ is equal to
max ( { 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ } ) . \max\bigl(\{1\}\cup\{|S|\mid S\subseteq D\text{ is expressive and belongs to a reversing block of }G_\Gamma\}\bigr). max ( { 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ } ) . Proof. Let c ′ = max ( { 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ } ) c'=\max(\{1\}\cup\{|S|\mid S\subseteq D\text{ is expressive and belongs to a reversing block of }G_\Gamma\}) c ′ = max ({ 1 } ∪ { ∣ S ∣ ∣ S ⊆ D is expressive and belongs to a reversing block of G Γ }) . Both c Γ c_\Gamma c Γ and c ′ c' c ′ are at least one: this holds for c ′ c' c ′ by definition, and for c Γ c_\Gamma c Γ because the constant unary function with value one is expressible. Let S S S be an expressive set belonging to a reversing block. Expressiveness gives all finite-valued unary cost functions on S S S , so by Corollary 6.11 (and using hard lists to penalize values outside S S S if necessary) we have c ′ ≤ c Γ c'\le c_\Gamma c ′ ≤ c Γ .
For the reverse inequality, assume that c Γ > 2 c_\Gamma>2 c Γ > 2 , since otherwise c ′ ≥ 1 c'\ge1 c ′ ≥ 1 suffices. By Definition 5.5 , there exists some set S ⊆ D S\subseteq D S ⊆ D of size c Γ c_\Gamma c Γ such that Γ \Gamma Γ expresses a binary disequality function f f f on S S S . In a gadget for f f f , remove all hard lists on the two distinguished variables (if such hard lists exist). This does not change the values on S 2 S^2 S 2 . The resulting binary function is finite on all of D 2 D^2 D 2 since all auxiliary variables can take at least one value not forbidden by a hard list. By adding an additive constant if necessary we obtain a nonnegative finite-valued function f ^ ∈ pow ( Γ ) \hat{f}\in\operatorname{pow}(\Gamma) f ^ ∈ pow ( Γ ) that agrees with f f f on S 2 S^2 S 2 up to a constant κ \kappa κ .
For each a ∈ S a\in S a ∈ S , pinning the second argument to a a a using a hard list gives the finite-valued unary function h a ( x ) = f ^ ( x , a ) h_a(x)=\hat{f}(x,a) h a ( x ) = f ^ ( x , a ) . On S S S , this function has value κ + 1 \kappa+1 κ + 1 at a a a and κ \kappa κ at every other element. Nonnegative weighted sums of these functions express all finite-valued unary cost functions on S S S up to a constant. In particular, no two distinct elements of S S S dominate one another, and f ^ \hat{f} f ^ witnesses interaction between every pair. Thus S S S is expressive and, by Lemma 2.10, belongs to one block. This block is reversing because f ^ \hat{f} f ^ is a reversing move on every two-element subset of S S S . Hence ∣ S ∣ ≤ c ′ |S|\le c' ∣ S ∣ ≤ c ′ , proving the reverse inequality. □ાષ્ટ્રીય
Removing Redundant Elements of Reversing Blocks.
Since we can solve nonreversing blocks in polynomial time, it remains to explain how our algorithm handles reversing blocks. It will turn out that these are hard. Nevertheless, we can do further nontrivial preprocessing, with the goal of ensuring that in the end, each available set of a variable belonging to a reversing block is expressive. For this purpose, we define when an available element is locally necessary. Intuitively, an element is locally necessary at a variable if some assignment to its neighbors makes it strictly cheaper than every other available element at that variable.
Definition 6.12 (Locally necessary). Let D D D be a finite domain and Γ \Gamma Γ a finite-valued hard-list language over D D D . Consider an instance I = ( V , C , t ) I=(V,\mathcal{C},t) I = ( V , C , t ) of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , and let L u L_u L u be the nonempty set of available elements at each variable u ∈ V u \in V u ∈ V . Fix a variable v ∈ V v \in V v ∈ V , and let N v N_v N v be its neighbors in the primal graph. Let C v \mathcal{C}_v C v be the family of finite-valued constraints involving v v v . For an assignment π : N v → D \pi:N_v \to D π : N v → D with π ( u ) ∈ L u \pi(u) \in L_u π ( u ) ∈ L u for every u ∈ N v u \in N_v u ∈ N v and an element d ∈ L v d \in L_v d ∈ L v , let π d \pi_d π d extend π \pi π by assigning d d d to v v v , and put
h v ( d , π ) = ∑ C ∈ C v weight ( C ) cost f ( C ) ( π d ( scope ( C ) ) ) . h_v(d,\pi)=\sum_{C\in\mathcal{C}_v}\operatorname{weight}(C)\operatorname{cost}_f(C)(\pi_d(\operatorname{scope}(C))). h v ( d , π ) = C ∈ C v ∑ weight ( C ) cost f ( C ) ( π d ( scope ( C ))) . An element a ∈ L v a \in L_v a ∈ L v is locally necessary at v v v if there is such an assignment π \pi π for which, for every b ∈ L v ∖ { a } b \in L_v \setminus\{a\} b ∈ L v ∖ { a } ,
h v ( a , π ) < h v ( b , π ) . h_v(a,\pi)<h_v(b,\pi). h v ( a , π ) < h v ( b , π ) . In other words, a a a is the unique minimizer over L v L_v L v for some available assignment to the neighbors of v v v .
An element that is not locally necessary can be forbidden at v v v without changing the optimum: for every available assignment to the neighbors, another element is at least as good. Note that the replacement element may depend on the neighbor assignment, as in related context-dependent substitution rules for CSPs [3 , 66 ] . For unary and binary cost functions, local necessity corresponds to a condition used by Koster, van Hoesel, and Kolen [56 ] for domain-reduction purposes in their treewidth-based algorithm. For unary and binary cost functions, failure of local necessity also corresponds to bottom-line dead-end elimination [28 , 71 ] , and more generally represents an instance of improving mappings [75 ] .
We can compute whether an element is locally necessary by using the following mixed integer linear program (MILP).
Mixed integer linear program 6.13 (Local necessity test). Let D D D be a finite domain and Γ \Gamma Γ a finite-valued hard-list language over D D D . Let I = ( V , C , t ) I=(V,\mathcal{C},t) I = ( V , C , t ) be an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , and let L u L_u L u be the nonempty set of available elements at each variable u ∈ V u \in V u ∈ V . Fix a variable v ∈ V v \in V v ∈ V and an element a ∈ L v a \in L_v a ∈ L v , and let N v N_v N v be the neighbors of v v v in the primal graph. Let C v \mathcal{C}_v C v be the family of finite-valued constraints involving v v v . For each C ∈ C v C \in\mathcal{C}_v C ∈ C v , identify repeated variables in its scope and place v v v first, obtaining a finite-valued cost function g C ( d , y ˉ ) g_C(d,\bar{y}) g C ( d , y ˉ ) on distinct variables. Let u C , 1 , … , u C , k C u_{C,1},\ldots,u_{C,k_C} u C , 1 , … , u C , k C be the other variables in the constraint scope, and put
Y C = L u C , 1 × ⋯ × L u C , k C . Y_C=L_{u_{C,1}}\times\cdots\times L_{u_{C,k_C}}. Y C = L u C , 1 × ⋯ × L u C , k C . If k C = 0 k_C=0 k C = 0 , then Y C Y_C Y C consists of the empty tuple.
We will use a binary indicator variable q u , d q_{u,d} q u , d for assigning d ∈ L u d \in L_u d ∈ L u to each neighbor u ∈ N v u \in N_v u ∈ N v , and a binary indicator variable p C , y ˉ p_{C,\bar{y}} p C , y ˉ for choosing y ˉ ∈ Y C \bar{y}\in Y_C y ˉ ∈ Y C in each constraint C ∈ C v C\in\mathcal{C}_v C ∈ C v . For each element b ∈ L v ∖ { a } b\in L_v\setminus\{a\} b ∈ L v ∖ { a } , define the cost difference
d a ( b , p ) = ∑ C ∈ C v weight ( C ) ∑ y ˉ ∈ Y C p C , y ˉ ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) . d_a(b,p)=\sum_{C\in\mathcal{C}_v}\operatorname{weight}(C)\sum_{\bar{y}\in Y_C}p_{C,\bar{y}}\bigl(g_C(b,\bar{y})-g_C(a,\bar{y})\bigr). d a ( b , p ) = C ∈ C v ∑ weight ( C ) y ˉ ∈ Y C ∑ p C , y ˉ ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) . This expression measures the cost difference between assigning b b b to the variable v v v and assigning a a a to the variable. It is linear in the tuple indicators p C , y ˉ p_{C,\bar{y}} p C , y ˉ , with rational coefficients. We also use a rational
variable ε \varepsilon ε for the common cost gap. The mixed integer linear program is then
m a x i m i z e ε \mathop{\mathrm{maximize}}\ \varepsilon maximize ε
subject to ∑ d ∈ L u q u , d = 1 for every u ∈ N v , ∑ y ˉ ∈ Y C p C , y ˉ = 1 for every C ∈ C v , ∑ y ˉ ∈ Y C , y j = d p C , y ˉ = q u C , j , d for every C ∈ C v , 1 ≤ j ≤ k C , d ∈ L u C , j , ε ≤ d a ( b , p ) for every b ∈ L v ∖ { a } , ε ≤ 1 , q u , d ∈ { 0 , 1 } for every u ∈ N v , d ∈ L u , p C , y ˉ ∈ { 0 , 1 } for every C ∈ C v , y ˉ ∈ Y C . (5) \begin{aligned}
\text{subject to}\quad&\sum_{d\in L_u} q_{u,d}=1 &&\text{for every }u\in N_v, \\
&\sum_{\bar{y}\in Y_C} p_{C,\bar{y}}=1 &&\text{for every }C\in C_v, \\
&\sum_{\substack{\bar{y}\in Y_C,\\ y_j=d}} p_{C,\bar{y}}=q_{u_C,j,d} &&\text{for every }C\in C_v,\ 1\leq j\leq k_C,\ d\in L_{u_C,j}, \\
&\varepsilon\leq d_a(b,p) &&\text{for every }b\in L_v\setminus\{a\}, \\
&\varepsilon\leq1, \\
&q_{u,d}\in\{0,1\} &&\text{for every }u\in N_v,\ d\in L_u, \\
&p_{C,\bar{y}}\in\{0,1\} &&\text{for every }C\in C_v,\ \bar{y}\in Y_C. \tag*{(5)}
\end{aligned} subject to d ∈ L u ∑ q u , d = 1 y ˉ ∈ Y C ∑ p C , y ˉ = 1 y ˉ ∈ Y C , y j = d ∑ p C , y ˉ = q u C , j , d ε ≤ d a ( b , p ) ε ≤ 1 , q u , d ∈ { 0 , 1 } p C , y ˉ ∈ { 0 , 1 } for every u ∈ N v , for every C ∈ C v , for every C ∈ C v , 1 ≤ j ≤ k C , d ∈ L u C , j , for every b ∈ L v ∖ { a } , for every u ∈ N v , d ∈ L u , for every C ∈ C v , y ˉ ∈ Y C . (5)
The optimum of this mixed integer linear program is positive if and only if element a a a is locally necessary. To see this, let us elaborate on the chosen constraints. Together with Constraint (9), Constraint (4) ensures that each neighbor of v v v in the primal graph is assigned exactly one domain element. Similarly, Constraints (5) and (10) ensure that each constraint scope has a unique assignment. Constraint (6) ensures that the assignments to the constraint scopes match the assignments to the neighbors of v v v . Constraint (7) guarantees that ε \varepsilon ε is positive only if, for the chosen assignment to the neighbors of v v v , assigning a a a is strictly better than assigning any other element in the available set of v v v . Finally, Constraint (8) is added to keep the objective bounded in all cases, without affecting whether there exists a positive optimum (strictly speaking this constraint is not actually necessary). Conversely, an assignment making a a a uniquely cheapest gives rise to a solution to the MILP with positive ε \varepsilon ε . For unary and binary cost functions, Mixed integer linear program 6.13 is (essentially) equivalent to the formulation of Koster, van Hoesel, and Kolen [55 Section 6.3.2] .
Of course, solving MILPs is NP-hard in general. One might hope that this specific MILP can be solved in polynomial time; however, this is not the case in general: there is a simple reduction from 3-SAT showing that, for a suitable Γ \Gamma Γ , deciding whether an available element is locally necessary at a specific variable is NP-hard. Thus, unless P = NP, we cannot test local necessity in polynomial time for every Γ \Gamma Γ . Hence, we work with the linear programming (LP) relaxation of Mixed integer linear program 6.13 instead. Naturally, similar linear programming relaxations have been studied for CSPs and VCSPs before, e.g., [14 , 52 , 54 , 26 ] .
Linear program 6.14 (Fractional local necessity test). Let D D D be a finite domain and Γ \Gamma Γ a finite-valued hard-list language over D D D . Let I = ( V , C , t ) I=(V,C,t) I = ( V , C , t ) be an instance of VCSP( Γ ) (\Gamma) ( Γ ) , and let L u L_u L u be the nonempty set of available elements at each variable u ∈ V u\in V u ∈ V . Fix a variable v ∈ V v\in V v ∈ V and an element a ∈ L v a\in L_v a ∈ L v . Let N v N_v N v be the neighbors of v v v in the primal graph, and let C v C_v C v be the family of finite-valued constraints involving v v v . For each C ∈ C v C\in C_v C ∈ C v , let Y C Y_C Y C be the product of the available sets of its other distinct variables, ordered as in Mixed integer linear program 6.13; with no other variables, it consists of the empty tuple. Relax Mixed integer linear program 6.13 for I I I , v v v , and a a a by replacing Constraints (9) and (10) with
0 ≤ q u , d ≤ 1 for every u ∈ N v , d ∈ L u , 0\leq q_{u,d}\leq1 \qquad\text{for every }u\in N_v,\ d\in L_u, 0 ≤ q u , d ≤ 1 for every u ∈ N v , d ∈ L u ,
0 ≤ p C , y ˉ ≤ 1 for every C ∈ C v , y ˉ ∈ Y C . 0\leq p_{C,\bar{y}}\leq1 \qquad\text{for every }C\in C_v,\ \bar{y}\in Y_C. 0 ≤ p C , y ˉ ≤ 1 for every C ∈ C v , y ˉ ∈ Y C .
All other constraints and the objective remain the same.
This gives us a fractional version of local necessity.
Definition 6.15 (Locally fractionally necessary). Let D D D be a finite domain and Γ \Gamma Γ a finite-valued hard-list language over D D D . Let I I I be an instance of VCSP( Γ ) (\Gamma) ( Γ ) in which every variable has a nonempty set of available elements. An element a a a available at a variable v v v of I I I is locally fractionally necessary at v v v if the optimum of Linear program 6.14 for I I I , v v v , and a a a is positive.
Clearly every feasible solution of the MILP is also feasible for its LP relaxation, with the same objective value. Thus the LP optimum is at least the MILP optimum, and we obtain the following observation.
Observation 6.16. Every element that is not locally fractionally necessary is not locally necessary. Forbidding it at its variable using hard lists preserves the optimum and the primal graph.
For unary and binary cost functions, our LP deletion criterion corresponds to the generalized Goldstein criterion [44 ] . Lasters, De Maeyer, and Desmet [62 ] apply this criterion in preprocessing using linear programming. Koster, van Hoesel, and Kolen also use an LP relaxation in their approach [55 Section 8.3] . The higher-arity LP deletion criterion we use also exactly fits within Shekhovtsov’s framework of relaxed improving mappings [75 ] .
The LP has rational coefficients, so exact rational linear programming determines its optimum in polynomial time. This directly yields the following preprocessing step.
Lemma 6.17. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D . Given an instance I I I of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , where the available set of each variable is nonempty, one can in polynomial time add hard-list constraints to obtain an instance I ′ I' I ′ with the same optimum and primal graph such that every available element is locally fractionally necessary at its variable.
Proof. While an available element is not locally fractionally necessary, forbid it at its variable by adding a hard list. By Observation 6.16, each deletion preserves the optimum and the primal graph. The LP has polynomial size because the domain, language, and arities are fixed, and its rational coefficients have polynomial bit length. Exact rational linear programming determines whether its optimum is positive in polynomial time. The sole element of an available set of size one is locally fractionally necessary, so no available set becomes empty. At most ( ∣ D ∣ − 1 ) ∣ V ∣ (|D|-1)|V| ( ∣ D ∣ − 1 ) ∣ V ∣ deletions occur, after which every available element is locally fractionally necessary. □
The LP deletion procedure subsumes the deletions in Lemmas 6.1 and 6.3, but we present these simpler steps first to expose the block structure and avoid running LPs on nonreversing blocks.
From Fractional Local Necessity to Expressive Sets.
With the preprocessing above, we can already see how the final algorithm will work. However, it remains to tie the size of the available sets that remain at the end of preprocessing to our notion of expressive sets. In this section, the goal is to show precisely this: after all of our preprocessing, each remaining available set is expressive.
Theorem 6.18. Let D D D be a finite domain and Γ \Gamma Γ a finite, finite-valued hard-list language over D D D , and B B B a reversing block of G Γ G_{\Gamma} G Γ . Let I I I be an instance of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) such that the available set L v L_v L v of each variable v v v :
belongs to B B B or has size one,
is pairwise interacting, and
has the property that each element of L v L_v L v is locally fractionally necessary at v v v .
Then, every available set of I I I is expressive.
Proof. For each variable u u u of I I I , write L u L_u L u for its available set, and let A \mathcal{A} A contain every nonempty subset of some L u L_u L u . By assumption, every member of A \mathcal{A} A of size at least two is pairwise interacting and belongs to B B B . We first show that, for each L ∈ A L \in\mathcal{A} L ∈ A , there is an instance J L J_L J L of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) with a variable x x x whose available set is L L L , such that every variable of J L J_L J L has an available set in A \mathcal{A} A and every a ∈ L a \in L a ∈ L is locally necessary at x x x in J L J_L J L .
Building instance J L J_L J L . If ∣ L ∣ = 1 |L|=1 ∣ L ∣ = 1 , take J L J_L J L to have only the variable x x x and a hard list on L L L . The claim holds because x x x has only one available element.
Now suppose ∣ L ∣ ≥ 2 |L| \ge2 ∣ L ∣ ≥ 2 and choose a variable v v v of I I I with L ⊆ L v L \subseteq L_v L ⊆ L v . In this case, for each a ∈ L a \in L a ∈ L , we use a solution to the LP that certifies that a a a is locally fractionally necessary at v v v to build the instance J L J_L J L . The basic idea is that although such a solution is fractional, we can create J L J_L J L by using sufficiently many copies of the variables to clear the denominators.
For each a ∈ L a \in L a ∈ L , local fractional necessity gives a rational solution of Linear program 6.14 for I I I , v v v , a a a with margin (i.e., objective ε \varepsilon ε of the LP) ε a > 0 \varepsilon_a > 0 ε a > 0 . Let C v \mathcal{C}_v C v be the family of finite-valued constraints involving v v v , and put w C = weight ( C ) w_C = \operatorname{weight}(C) w C = weight ( C ) for C ∈ C v C \in\mathcal{C}_v C ∈ C v . After identifying repeated variables and placing v v v first, write g C ( d , y ˉ ) g_C(d,\bar{y}) g C ( d , y ˉ ) for the cost of C C C with v v v assigned d d d , and let Y C Y_C Y C be the product of the available sets of its other distinct variables, ordered as in Linear program 6.14. Denote the assignments to the variables p C , y ˉ p_{C,\bar{y}} p C , y ˉ in the chosen solution for a a a by p C , y ˉ a p_{C,\bar{y}}^{a} p C , y ˉ a . For every b ∈ L ∖ { a } b \in L \setminus\{a\} b ∈ L ∖ { a } , Constraint (7) of the LP gives
∑ C ∈ C v w C ∑ y ˉ ∈ Y C p C , y ˉ a ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) ≥ ε a > 0. \sum_{C \in\mathcal{C}_{v}} w_C \sum_{\bar{y} \in Y_C} p_{C,\bar{y}}^{a}\left(g_C(b,\bar{y})-g_C(a,\bar{y})\right) \ge\varepsilon_a > 0. C ∈ C v ∑ w C y ˉ ∈ Y C ∑ p C , y ˉ a ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) ≥ ε a > 0.
Choose a positive integer N N N such that N w C Nw_C N w C and N w C p C , y ˉ a Nw_Cp_{C,\bar{y}}^{a} N w C p C , y ˉ a are integers for every a a a , C C C , and y ˉ \bar{y} y ˉ . Construct J L J_L J L with a variable x x x restricted to L L L by a hard list. For each C ∈ C v C \in\mathcal{C}_v C ∈ C v , add N w C Nw_C N w C unit-weight copies of the original constraint C C C , using x x x wherever C C C uses v v v and fresh variables for its other distinct variables in each copy. Preserve repeated occurrences of each variable within a copy, and give every fresh variable the available set of the corresponding variable of I I I by a hard list. Thus every variable other than x x x has an available set in A \mathcal{A} A .
For each a ∈ L a \in L a ∈ L and C ∈ C v C \in\mathcal{C}_v C ∈ C v , assign the other variables in exactly N w C p C , y ˉ a Nw_Cp_{C,\bar{y}}^{a} N w C p C , y ˉ a copies of C C C the tuple y ˉ \bar{y} y ˉ , for each y ˉ ∈ Y C \bar{y} \in Y_C y ˉ ∈ Y C . These counts sum to N w C Nw_C N w C , and the variables in different copies are distinct, so this defines an available assignment π a \pi^a π a to all variables of J L J_L J L other than x x x . Changing x x x from a a a to any b ∈ L ∖ { a } b \in L \setminus\{a\} b ∈ L ∖ { a } under this assignment changes the cost by
N ∑ C ∈ C v w C ∑ y ˉ ∈ Y C p C , y ˉ a ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) ≥ N ε a > 0. N \sum_{C \in\mathcal{C}_{v}} w_C \sum_{\bar{y} \in Y_C} p_{C,\bar{y}}^{a}\left(g_C(b,\bar{y})-g_C(a,\bar{y})\right) \ge N\varepsilon_a > 0. N C ∈ C v ∑ w C y ˉ ∈ Y C ∑ p C , y ˉ a ( g C ( b , y ˉ ) − g C ( a , y ˉ ) ) ≥ N ε a > 0.
Hence every a ∈ L a \in L a ∈ L is locally necessary at x x x in this same instance J L J_L J L .
Expressing cost functions. We now prove by induction on k ≥ 1 k \ge1 k ≥ 1 that Γ \Gamma Γ expresses all finite-valued unary cost functions on every L ∈ A L \in\mathcal{A} L ∈ A with ∣ L ∣ ≤ k |L| \le k ∣ L ∣ ≤ k . By Corollary 6.11, this also gives all nonnegative rational-valued cost functions, up to a constant, on products of such sets.
If ∣ L ∣ = 1 |L|=1 ∣ L ∣ = 1 any unary cost is constant, so the zero unary function suffices up to a constant. If ∣ L ∣ = 2 |L|=2 ∣ L ∣ = 2 , interaction excludes domination in either direction, and Lemma 4.5 gives all unary costs on L L L . This establishes the induction claim for k ≤ 2 k \le2 k ≤ 2 .
Suppose the claim holds for sizes below k ≥ 3 k \ge3 k ≥ 3 , and fix L ∈ A L \in\mathcal{A} L ∈ A of size k k k and a 0 ∈ L a_0 \in L a 0 ∈ L . Take the instance J L J_L J L above with variable x x x , and enumerate its other variables as y 1 , … , y s y_1,\ldots,y_s y 1 , … , y s . For each a ∈ L a \in L a ∈ L , let y ˉ a \bar{y}^{a} y ˉ a be their values under π a \pi^a π a . Write F ( d , y ˉ ) F(d,\bar{y}) F ( d , y ˉ ) for the sum of the finite-valued constraint costs of J L J_L J L when x x x receives d d d and the other variables receive y ˉ \bar{y} y ˉ . Then
F ( a , y ˉ a ) < F ( b , y ˉ a ) for every a ∈ L and b ∈ L ∖ { a } . F(a,\bar{y}^{a}) < F(b,\bar{y}^{a}) \qquad\text{for every } a \in L \text{ and } b \in L \setminus\{a\}. F ( a , y ˉ a ) < F ( b , y ˉ a ) for every a ∈ L and b ∈ L ∖ { a } .
The tuples y ˉ a \bar{y}^{a} y ˉ a are pairwise distinct, since two distinct elements cannot both be uniquely cheapest under the same assignment; in particular, s ≥ 1 s \ge1 s ≥ 1 .
For i ∈ [ s ] i \in[s] i ∈ [ s ] , put
T i = { π a ( y i ) ∣ a ∈ L ∖ { a 0 } } , T_i = \{\pi^a(y_i) \mid a \in L \setminus\{a_0\}\}, T i = { π a ( y i ) ∣ a ∈ L ∖ { a 0 }} ,
and let P = T 1 × ⋯ × T s P=T_1 \times\cdots\times T_s P = T 1 × ⋯ × T s . Each T i T_i T i is a nonempty subset of the available set of y i y_i y i in J L J_L J L , so T i ∈ A T_i \in\mathcal{A} T i ∈ A . Moreover, ∣ T i ∣ ≤ k − 1 |T_i| \le k-1 ∣ T i ∣ ≤ k − 1 by its definition. Put
K = max d ∈ L , y ˉ ∈ P F ( d , y ˉ ) . K = \max_{d \in L,\ \bar{y} \in P} F(d,\bar{y}). K = d ∈ L , y ˉ ∈ P max F ( d , y ˉ ) .
Define the nonnegative function g ^ : P → Q ≥ 0 \hat{g}:P \to\mathbb{Q}_{\ge0} g ^ : P → Q ≥ 0 by
g ^ ( y ˉ ) = { K − F ( a , y ˉ a ) , y ˉ = y ˉ a for some a ∈ L ∖ { a 0 } , 2 K + 1 , otherwise. \hat{g}(\bar{y}) =
\begin{cases}
K-F(a,\bar{y}^{a}), & \bar{y}=\bar{y}^{a}\text{ for some }a \in L\setminus\{a_0\},\\
2K+1, & \text{otherwise.}
\end{cases} g ^ ( y ˉ ) = { K − F ( a , y ˉ a ) , 2 K + 1 , y ˉ = y ˉ a for some a ∈ L ∖ { a 0 } , otherwise.
This function is well-defined since the tuples y ˉ a \bar{y}^{a} y ˉ a and y ˉ a ′ \bar{y}^{a'} y ˉ a ′ are distinct for a ≠ a ′ a \ne a' a = a ′ . By the induction hypothesis and Corollary 6.11, there are a finite-valued g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) and a constant c ∈ Q c \in\mathbb{Q} c ∈ Q with g ( y ˉ ) = g ^ ( y ˉ ) + c g(\bar{y})=\hat{g}(\bar{y})+c g ( y ˉ ) = g ^ ( y ˉ ) + c for all y ˉ ∈ P \bar{y} \in P y ˉ ∈ P .
Keep the finite-valued constraints of J L J_L J L , restrict each y i y_i y i to T i T_i T i by a hard list, and add a gadget for g g g with inputs y 1 , … , y s y_1,\ldots,y_s y 1 , … , y s . Do not impose a hard list on x x x . Minimizing over all variables other than x x x gives a unary function h ∈ pow ( Γ ) h \in\operatorname{pow}(\Gamma) h ∈ pow ( Γ ) that fulfills, for all d ∈ L d \in L d ∈ L ,
h ( d ) = min y ˉ ∈ P ( F ( d , y ˉ ) + g ( y ˉ ) ) . h(d)=\min_{\bar{y}\in P}\left(F(d,\bar{y})+g(\bar{y})\right). h ( d ) = y ˉ ∈ P min ( F ( d , y ˉ ) + g ( y ˉ ) ) .
This function is finite-valued on all of D D D : P P P is nonempty, and both F F F and g g g have finite values there. For d ∈ L d \in L d ∈ L , a tuple y ˉ ∈ P \bar{y} \in P y ˉ ∈ P not among { y ˉ a ∣ a ∈ L ∖ { a 0 } } \{\bar{y}^{a} \mid a \in L \setminus\{a_{0}\}\} { y ˉ a ∣ a ∈ L ∖ { a 0 }} has F ( d , y ˉ ) + g ^ ( y ˉ ) ≥ 2 K + 1 F(d,\bar{y})+\hat{g}(\bar{y}) \ge2K+1 F ( d , y ˉ ) + g ^ ( y ˉ ) ≥ 2 K + 1 , while every y ˉ a \bar{y}^{a} y ˉ a with a ≠ a 0 a \ne a_{0} a = a 0 has F ( d , y ˉ a ) + g ^ ( y ˉ a ) ≤ 2 K F(d,\bar{y}^{a})+\hat{g}(\bar{y}^{a}) \le2K F ( d , y ˉ a ) + g ^ ( y ˉ a ) ≤ 2 K . Therefore
h ( d ) = c + K + min a ∈ L ∖ { a 0 } ( F ( d , y ˉ a ) − F ( a , y ˉ a ) ) ( d ∈ L ) . h(d)=c+K+\min_{a\in L\setminus\{a_{0}\}}\left(F(d,\bar{y}^{a})-F(a,\bar{y}^{a})\right) \qquad(d\in L). h ( d ) = c + K + a ∈ L ∖ { a 0 } min ( F ( d , y ˉ a ) − F ( a , y ˉ a ) ) ( d ∈ L ) .
We have that min a ∈ L ∖ { a 0 } ( F ( d , y ˉ a ) − F ( a , y ˉ a ) ) \min_{a\in L\setminus\{a_{0}\}}\left(F(d,\bar{y}^{a})-F(a,\bar{y}^{a})\right) min a ∈ L ∖ { a 0 } ( F ( d , y ˉ a ) − F ( a , y ˉ a ) ) is zero when d ∈ L ∖ { a 0 } d \in L \setminus\{a_{0}\} d ∈ L ∖ { a 0 } , and is the positive rational number
δ = min a ∈ L ∖ { a 0 } ( F ( a 0 , y ˉ a ) − F ( a , y ˉ a ) ) \delta=\min_{a\in L\setminus\{a_{0}\}}\left(F(a_{0},\bar{y}^{a})-F(a,\bar{y}^{a})\right) δ = a ∈ L ∖ { a 0 } min ( F ( a 0 , y ˉ a ) − F ( a , y ˉ a ) )
when d = a 0 d=a_{0} d = a 0 . Scaling h h h by 1 / δ 1/\delta 1/ δ thus gives, up to a constant shift, the unary cost that is one at a 0 a_{0} a 0 and zero at every other element of L L L . Repeating this construction for each a 0 ∈ L a_{0} \in L a 0 ∈ L and taking nonnegative weighted sums gives all finite-valued unary cost functions on L L L , up to a constant, completing the induction.
For every available set L v L_{v} L v of I I I , the induction shows that Γ \Gamma Γ expresses all finite-valued unary cost functions on L v L_{v} L v . Since L v L_{v} L v is pairwise interacting by assumption, it is expressive by the remark after the restatement of Definition 2.11 at the start of § 6 .
The preceding theorem lets us obtain an algorithm where the running-time base directly corresponds to the size of expressive sets belonging to reversing blocks. Now, we are ready to provide our algorithm for finite-valued hard-list languages.
Theorem 6.19. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite, finite-valued hard-list language over D D D . Given an instance I I I of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) and a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , one can compute Opt ( I ) \operatorname{Opt}(I) Opt ( I ) and an assignment attaining it in time
( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (c_{\Gamma})^{\operatorname{tw}}\cdot(|I|+|\mathcal{T}|)^{O(1)}. ( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) .
Proof. If some variable has no available element, then I I I has no finite-cost assignment, so return the value ∞ \infty ∞ with an arbitrary variable assignment. Otherwise apply Lemma 6.3 to obtain nonempty, pairwise interacting available sets. The optimum and primal graph are preserved. By Lemma 6.9 , separate the instance into block instances, recording their additive constant and transforming the supplied tree decomposition with at most a constant increase in width. The block instances use the original language Γ \Gamma Γ , and their auxiliary variables have available sets of size one. Compute the optimum and an optimal assignment for every nonreversing block in polynomial time by Lemma 6.10 .
For each reversing block B B B , apply Lemma 6.17 to its block instance. All remaining available sets are still pairwise interacting, and each set of size at least two still belongs to B B B , since these properties are inherited by subsets. By Theorem 6.18 , every remaining available set is expressive and therefore has size at most c Γ c_{\Gamma} c Γ by Lemma 2.12 . The LP step only adds hard-list constraints, so the primal treewidth remains bounded by tw + O ( 1 ) \operatorname{tw}+O(1) tw + O ( 1 ) .
Using Lemma 2.8 , compute the optimum and an optimal assignment of each reversing block instance in time ( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) (c_{\Gamma})^{\operatorname{tw}}\cdot(|I|+|\mathcal{T}|)^{O(1)} ( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , where we use that c Γ c_{\Gamma} c Γ is a fixed constant. There are only constantly many blocks, since D D D and Γ \Gamma Γ are fixed. Add their optimum values and the recorded constant, and combine their optimal assignments with the original singleton values as in Lemma 6.9 .
The Main Theorem
Now, we are ready for the proof of Theorem 1.1.
Theorem 1.1. Let D D D be a fixed finite domain and Γ \Gamma Γ a fixed finite-valued hard-list language over D D D .
There is an algorithm that, given a VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) instance I I I together with a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , solves I I I in time
( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . (c_{\Gamma})^{\operatorname{tw}}\cdot(|I|+|\mathcal{T}|)^{O(1)}. ( c Γ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) . If c Γ ≥ 2 c_{\Gamma} \ge2 c Γ ≥ 2 , for every ϵ > 0 \epsilon>0 ϵ > 0 , there is no algorithm that solves an instance I I I of VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) , given together with a tree decomposition T \mathcal{T} T of its primal graph of width tw \operatorname{tw} tw , in time
( c Γ − ϵ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , (c_{\Gamma}-\epsilon)^{\operatorname{tw}}\cdot(|I|+|\mathcal{T}|)^{O(1)}, ( c Γ − ϵ ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) , unless tw \operatorname{tw} tw -SETH is false. The same lower bound holds under pw \operatorname{pw} pw -SETH with treewidth replaced by pathwidth.
Proof. We obtain statement (1) from Theorem 6.19 . For (2), assume that tw \operatorname{tw} tw -SETH (pw \operatorname{pw} pw -SETH, respectively) holds and that c Γ ≥ 2 c_{\Gamma} \ge2 c Γ ≥ 2 . Then, Lemma 5.6 gives (2).
AI Usage
The proof of the main result of this paper has been obtained from several conversations with GPT-5.6 Sol and GPT-6 Astra based on our notes and partial results. The draft has been written with the help of various large language models (also including GPT-6.1 Sol), which were also used for the purpose of literature search. The introduction and technical overview were written by the authors. The content has been checked and curated by humans, and the authors take full responsibility for the content of the article.
Restricting the Domain of Γ \Gamma Γ vs. pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ )
Theorem 1.1 shows that the complexity of the problem is determined by the maximum size c Γ c_{\Gamma} c Γ of a set S ⊆ D S \subseteq D S ⊆ D on which pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains a disequality function. In a sense, this means that Γ \Gamma Γ has a “core” S S S on which VCSP is as hard as possible, i.e., requires ∣ S ∣ t w ⋅ n O ( 1 ) |S|^{\mathrm{tw}} \cdot n^{O(1)} ∣ S ∣ tw ⋅ n O ( 1 ) time. The following example clarifies that this does not necessarily mean that if we restrict every relation in Γ \Gamma Γ to S S S , then we get a language Γ S \Gamma_{S} Γ S with the same complexity, also requiring ∣ S ∣ t w ⋅ n O ( 1 ) |S|^{\mathrm{tw}} \cdot n^{O(1)} ∣ S ∣ tw ⋅ n O ( 1 ) time. It is possible that in order to express the disequality function on S S S appearing in pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) , we need to rely on values outside S S S .
Example A.1. Let D = { 0 , 1 , 2 } D = \{0,1,2\} D = { 0 , 1 , 2 } , and let Γ \Gamma Γ be the finite-valued hard-list language consisting of all hard lists and the binary cost function f ( x , y ) f(x,y) f ( x , y ) defined by the table
Table 1.
where rows give the first argument and columns the second. Using hard lists we can obtain the unary cost functions f ( ⋅ , 0 ) = ( 0 , 1 , 2 ) f(\cdot,0) = (0,1,2) f ( ⋅ , 0 ) = ( 0 , 1 , 2 ) , f ( ⋅ , 1 ) = ( 0 , 2 , 1 ) f(\cdot,1) = (0,2,1) f ( ⋅ , 1 ) = ( 0 , 2 , 1 ) , and f ( 2 , ⋅ ) = ( 2 , 1 , 0 ) f(2,\cdot) = (2,1,0) f ( 2 , ⋅ ) = ( 2 , 1 , 0 ) . Here each triple gives the function’s costs at the domain values 0, 1, 2, respectively. These provide strict preferences in both directions on every pair, so no distinct values dominate one another. Each pair of domain elements also witnesses its own interaction through f f f , so all three pairs belong to one block by Lemma 2.10.
Nevertheless, for every c ∈ D c \in D c ∈ D we have
f ( 1 , c ) ≥ f ( 0 , c ) + f ( 2 , c ) 2 , f ( c , 1 ) ≥ f ( c , 0 ) + f ( c , 2 ) 2 . f(1,c) \ge\frac{f(0,c)+f(2,c)}{2}, \qquad f(c,1) \ge\frac{f(c,0)+f(c,2)}{2}. f ( 1 , c ) ≥ 2 f ( 0 , c ) + f ( 2 , c ) , f ( c , 1 ) ≥ 2 f ( c , 0 ) + f ( c , 2 ) . Moreover, f ( 1 , 1 ) = 2 ≥ 0 = ( f ( 0 , 0 ) + f ( 2 , 2 ) ) / 2 f(1,1) = 2 \ge0 = (f(0,0)+f(2,2))/2 f ( 1 , 1 ) = 2 ≥ 0 = ( f ( 0 , 0 ) + f ( 2 , 2 )) /2 as well.
Now, consider an arbitrary instance of the problem. Let v v v be a variable whose available set is D D D , and let h v ( d , π ) h_v(d,\pi) h v ( d , π ) be the total cost of the constraints that contain v v v when assigning d d d to v v v and π \pi π to the neighbors of v v v in the primal graph. Summing the inequalities gives
h v ( 1 , π ) ≥ h v ( 0 , π ) + h v ( 2 , π ) 2 . h_v(1,\pi) \ge\frac{h_v(0,\pi)+h_v(2,\pi)}{2}. h v ( 1 , π ) ≥ 2 h v ( 0 , π ) + h v ( 2 , π ) . Thus either 0 or 2 can replace 1 without increasing the cost, although the choice may depend on π \pi π . In fact, when any variable of any instance has all of D D D as its available set, then the element 1 is not locally fractionally necessary. The preprocessing therefore leaves available sets of size at most two, so Lemma 2.8 gives running time 2 t w ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) 2^{\mathrm{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)} 2 tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) for an instance I I I with a supplied tree decomposition T \mathcal{T} T of width t w \mathrm{tw} tw .
For a nonempty proper subset S ⊊ D S \subsetneq D S ⊊ D , let Γ S \Gamma_{S} Γ S be obtained by restricting every function of Γ \Gamma Γ to S S S . Every problem VCSP ( Γ S ) \operatorname{VCSP}(\Gamma_{S}) VCSP ( Γ S ) is polynomial-time solvable. On { 0 , 1 } \{0,1\} { 0 , 1 } , value 0 dominates 1; on { 1 , 2 } \{1,2\} { 1 , 2 } , value 2 dominates 1. Deleting the dominated value whenever both are available fixes every variable. On { 0 , 2 } \{0,2\} { 0 , 2 } , the only positive entry is f ( 2 , 0 ) = 2 f(2,0)=2 f ( 2 , 0 ) = 2 , so the problem is a weighted directed minimum-cut problem. The hard lists force some vertices to be on a specific side of the cut, which is easy to handle.
In contrast, pow ( Γ ) \operatorname{pow}(\Gamma) pow ( Γ ) contains the disequality function on { 0 , 1 } \{0,1\} { 0 , 1 } . To see this, let ℓ S \ell_{S} ℓ S denote the hard-list cost function that is 0 on S S S and ∞ \infty ∞ outside S S S , and define
g ( x , y ) = ℓ { 0 , 1 } ( x ) + ℓ { 0 , 1 } ( y ) + min p ∈ D ( 2 f ( x , y ) + 3 f ( p , x ) + f ( p , y ) + ℓ { 2 } ( p ) ) − 7. g(x,y) = \ell_{\{0,1\}}(x) + \ell_{\{0,1\}}(y) + \min_{p \in D}(2f(x,y) + 3f(p,x) + f(p,y) + \ell_{\{2\}}(p)) - 7. g ( x , y ) = ℓ { 0 , 1 } ( x ) + ℓ { 0 , 1 } ( y ) + p ∈ D min ( 2 f ( x , y ) + 3 f ( p , x ) + f ( p , y ) + ℓ { 2 } ( p )) − 7. The hard list forces p = 2 p = 2 p = 2 , and the weighted sum is 8 at ( x , y ) = ( 0 , 0 ) , ( 1 , 1 ) (x,y) = (0,0),(1,1) ( x , y ) = ( 0 , 0 ) , ( 1 , 1 ) and 7 at ( x , y ) = ( 0 , 1 ) , ( 1 , 0 ) (x,y) = (0,1),(1,0) ( x , y ) = ( 0 , 1 ) , ( 1 , 0 ) . Thus g ( x , x ) = 1 g(x,x) = 1 g ( x , x ) = 1 for x ∈ { 0 , 1 } x \in\{0,1\} x ∈ { 0 , 1 } and g ( x , y ) = 0 g(x,y) = 0 g ( x , y ) = 0 for distinct x , y ∈ { 0 , 1 } x,y \in\{0,1\} x , y ∈ { 0 , 1 } , while g g g is infinite outside { 0 , 1 } 2 \{0,1\}^{2} { 0 , 1 } 2 . In particular, g g g is nonnegative, so the additive shift is allowed and g ∈ pow ( Γ ) g \in\operatorname{pow}(\Gamma) g ∈ pow ( Γ ) . Hence c Γ ≥ 2 c_{\Gamma} \ge2 c Γ ≥ 2 , and Theorem 1.1 rules out an algorithm for VCSP ( Γ ) \operatorname{VCSP}(\Gamma) VCSP ( Γ ) running in time ( 2 − ε ) t w ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) (2-\varepsilon)^{\mathrm{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)} ( 2 − ε ) tw ⋅ ( ∣ I ∣ + ∣ T ∣ ) O ( 1 ) for any ε > 0 \varepsilon> 0 ε > 0 , unless tw-SETH is false. This matches the upper bound above, even though every proper domain restriction is polynomial-time solvable: the gadget expressing disequality on { 0 , 1 } \{0,1\} { 0 , 1 } uses the auxiliary value 2. The same gadget also gives NP-hardness by a reduction from Max Cut [43 ] , since placing it on every edge of a graph G G G gives total cost 8 ∣ E ( G ) ∣ 8|E(G)| 8∣ E ( G ) ∣ minus the cut size before the additive shifts. Therefore, unless P = NP, the full problem cannot reduce in polynomial time to any single proper domain restriction Γ S \Gamma_{S} Γ S .