Preserving Partial Solutions While Relaxing Constraint Networks

1 Introduction

CSP optimization frameworks extend the basic setting of constraint satisfaction by supporting the definition of an objective function over the space of all possible solutions (see, e.g., [Rossi et al., 2006; Bistarelli et al., 1999]). In some cases, however, more than just one function has to be optimized, so that some form of multi-objective optimization comes into play. For instance, in a configuration problem, the customer might have different functions to optimize, including the price and her preferences over the various features of the product.

Two forms of multi-objective optimization have been already considered in the CSP literature, giving rise to lexicographic (see, e.g., [Freuder et al., 2010; Greco and Scarcello, 2011]) and Pareto (see, e.g., [Torrens and Faltings, 2002]) optimization settings. By abstracting from their peculiarities, these approaches share the idea of looking at the optimization problem from a "global" perspective, by tolerating poor values over some functions provided they are compensated by excellent values over the others. There are several application domains, however, where this perspective is not desirable and a "fair" approach to multi-objective optimization would be more appropriate. A noticeable example comes from fair allocation problems (see, e.g., [Bez´akov´a and Dani, 2005]) and, more generally, from applications in multi-agent systems, where different agents have differentpossibly contrasting-objective functions to optimize and the goal is to compute a socially desirable solution [Brandt et al., 2012]. In fact, there are different possible notions of fairness, which may be more or less appropriate depending on the specific application. In this paper, we focus on the MAX-MIN approach, where fairness means maximizing the value associated with the least satisfied function/agent/goal.

Example 1.1. Consider the left part of Figure 1, which shows a setting where four indivisible and non-sharable resources R1, ..., R4 have to be allocated to three agents a1, a2, and a3. Each agent reports not only which resources are of interest to her (represented as the edges incident on the agent), but also a degree of preference over them (represented as edge weights). Agent preferences are additive over the various resources, and we assume that no agent can get more than two resources. Then, the goal is to compute a fair allocation, meaning an allocation where the total weight of the resources assigned to the least satisfied agent is maximized. 1

For instance, the least satisfied agent in the allocation θ1 in Figure 1 is a3. In fact, θ1 is preferable to θ2 according to this perspective, even though the overall value achieved with θ2 (5+9+1) is greater than the one achieved in θ1 (5+4+3). ✁

A few approaches for fair CSP optimization have already been proposed in the literature (see, e.g., [Snow and Freuder, 1990; Dubois and Fortemps, 1999; Bouveret and Lematre, 2009]), where in particular each function can be defined over one constraint or one variable only. In fact, a general model was missing, which is capable to handle the large variety of optimization functions considered in standard CSP optimization [Rossi et al., 2006; Bistarelli et al., 1999]. Moreover, the complexity issues arising with fair optimization and the identification of islands of tractability, i.e., of classes of instances that are efficiently solvable, have been unexplored. Our goal with the paper is precisely to fill this gap. In particular,

• We define a MAX-MIN framework with powerful modeling capabilities, where the goal is to maximize the objective function getting the minimum value, and where such

1 This is known as (a variant of) the Santa Claus problem [Bansal and Sviridenko, 2006], with Santa's goal being to distribute presents in a way that the least lucky kid is as happy as possible.

functions can involve an arbitrary number of constraints and are defined via suitable algebraic operators (as in standard constraint optimization). In order to get a higher level of fairness, we also consider the LEXMAX-MIN framework where, over all solutions maximizing the minimum value, we look for those maximizing the second minimum value and so on, in a lexicographical MAX-MIN perspective.

• Since (fair) constraint optimization is NP-hard in general, we first focus on the class of acyclic instances, which forms a well-known island of tractability for plain CSPs. It turns out that acyclicity does not suffice alone to guarantee tractability in our settings. Motivated by the bad news, we then look for tractable classes via restrictions on the number of optimization functions involved and/or the size of their domains, and chart the tractability frontier w.r.t. them.
• Finally, we propose a more powerful method to identify larger islands of tractability where the "structure" of the optimization functions is taken into account together with the structure of the underlying CSP instance. In particular, we define the notion of guarded instances and show that, for such nearly-acyclic instances, optimal (LEX)MAX-MIN solutions can be efficiently computed without restrictions on the number of optimization functions or on their domains.

2 Formal Framework

Constraint Satisfaction (see,e.g.,[Dechter, 2003]). Let Var be a set of variables and let U be a set of constants. We use the logic-based characterization of CSPs [Kolaitis and Vardi, 2000; Scarcello et al., 2008]. Therefore, a CSP instance is viewed as a pair (Φ, DB), where DB is a constraint database, i.e., a finite set of ground atoms of the form ri(c1, ..., ck) with cj ∈ U, for each j ∈ {1, ..., k}, and where Φ is a constraint formula, i.e., a conjunction of atoms r1(u1) ∧ · · · ∧ rm(um) such that u1, ..., um are lists of terms, that is, variables in Var or constants in U. A solution to the instance (Φ, DB) is a substitution θ : X ↦→ U such that X = Var and rj(θ(uj)) ∈ DB, for each atom rj(uj) in Φ. 2 The set of all solutions to (Φ,DB) is denoted by ΦDB . A substitution θ : X ↦→ U is partial if it is undefined on some variable, i.e., X ⊂ Var . We often denote θ : X ↦→ U extensively, i.e., as the set of all pairs of the form X/c, where c = θ(X), for each X ∈ X .

Example 2.1. The setting of Example 1.1 can be formalized as a CSP instance (Φ, DB) over a domain U = {a1, a2, a3} of constants corresponding to the agents plus the fresh constant '-', and over a set Var = {R1, R2, R3, R4} of variables corresponding to the resources. In particular, let Uj ⊆ U be the set of all agents requiring Rj plus the constant '-' (no agent), for each j ∈ {1, ..., 4}. Then, (Φ, DB) is such that:

2 As usual, θ(uj) denotes the list (θ(u1), . . . , θ(um)).

where reqi in Φ is defined over the variables/resources that are required by agent ai, for each i ∈ {1, 2, 3}.

Note that in any solution θ, each resource can be mapped via θ to one agent chosen among those that are actually requiring it, and no agent can get more than two resources, with the constant '-' meaning that the resource is not allocated.

Consider now the four substitutions θ1 = {R1/a1, R2/a2, R3/a3, R4/a3}, θ2={R1/a1, R2/-, R3/a2, R4/a3}, θ3 = {R1/a2,R2/a1,R3/a3,R4/a3}, and θ4 = {R1/a1, R2/a3,R3/a3,R4/a3}. Note that θ1, θ2, and θ3 are three solutions (corresponding to the allocations in Figure 1), while θ4 is not a solution because agent a3 gets three resources. ✁

MAX-MIN and LEXMAX-MIN Optimization. The basic setting for constraint satisfaction is now extended by considering a MAX-MIN optimization framework defined on top of a set of valuation functions over the possible substitutions.

A valuation function F is a tuple 〈w,⊕〉 where w : ¯X × U ↦→ R, with ¯X ⊆ Var, is a real valued function over variable assignments and where ⊕ is a commutative, associative, and closed binary operator over a set D ⊆ R of real numbers that includes the identity element ⊥ w.r.t. ⊕ (e.g., 0 w.r.t. +, 1 w.r.t. ×, etc.). We assume also that ⊕ is distributive over the standard 'max' operator for real numbers. The set ¯X is called the domain of F, and it will be denoted by dom(F). For a (possibly partial) substitution θ : X ↦→ U, define

Example 2.2. In our running example, each agent ai can be equipped with a valuation function Fi = 〈wi, +〉 whose domain dom(Fi) = {Rj | ai ∈ Uj} consists of all the resources/variables that are desired by agent ai. Moreover, wi is such that wi(Rj/c) = 0, for each c ̸= ai, while wi(Rj/ai) is the worth for agent ai getting the resource Rj, i.e., the weight associated with the edge between ai and Rj in Figure 1. For instance, we have F1(θ1) = w1(R1/a1) = 5, while F3(θ1) = w3(R3/a3) +w3(R4/a3) = 2+1 = 3. ✁

Valuation functions are now combined to look for solutions maximizing the minimum value achieved over them.

Definition 2.3. Let (Φ, DB) be a CSP instance, let L be a set of valuation functions, and consider the following value:

A substitution θ ∈ ΦDB is a MAX-MIN solution to (Φ, DB) w.r.t. L if minF∈LF(θ) = MAX-MIN-VAL(Φ,DB,L). ✷

Example 2.4. By looking again at Figure 1, we can check that mini∈{1,2,3} Fi(θ1) = mini∈{1,2,3} Fi(θ3) = 3, while mini∈{1,2,3} Fi(θ2) = 1. In fact, it can be seen that θ1 and θ3 are both MAX-MIN solutions. ✁

By definition, MAX-MIN solutions are sensible to the minimum satisfaction level only. A lexicographic refinement is hence considered next to achieve a higher level of fairness.

Let L be a set of valuation functions. For any θ ∈ ΦDB , we denote by L(θ) the non-decreasingly sorted vector containing the value F(θ), for each F ∈ L. Such vectors will be compared via the binary operator '≻': For two vectors (v1, ..., vm) and (v′1 , ..., v′m), (v1, ..., vm) ≻ (v′1 , ..., v′m) holds if there is an integer j ∈ {0, ...,m - 1} such that vi = v′i , for each 1 ≤ i ≤ j, and vj+1 > v′j+1 . Moreover, for a set of vectors S, we define maxS as the vector ¯ v ∈ S such that ¯ v ≻ ¯ v′ , for each ¯ v′ ∈ S.

Definition 2.5. Let (Φ,DB) be a CSP instance, and let L be a set of valuation functions. A substitution θ ∈ ΦDB is a LEXMAX-MIN solution to (Φ,DB) w.r.t. L if L(θ) = max{L(θ′ ) | θ′ ∈ ΦDB}. ✷

Example 2.6. Let L = {F1, F2, F3} be the set of the valuation functions in our running example, and note that L(θ1) = (3, 4, 5) and L(θ3) = (3, 3, 5). Therefore, L(θ1) ≻ L(θ3) holds. In fact, θ1 is a LEXMAX-MIN solution. ✁

Problems Definition and Complexity Setting. In the paper, we analyze the complexity of the problem of computing MAX-MIN (resp., LEXMAX-MIN) solutions to CSP instances, hereinafter referred to as problem MAX-MIN-CSP (resp., LEXMAX-MIN-CSP), for short. The problem receives as input a triple (Φ, DB, L), where (Φ, DB) is a CSP instance and L is a set of valuation functions. In the analysis, we assume that functions are listed in the input, and that the underlying binary operators are polynomial-time computable.

Towards a finer grained analysis, different classes of sets of valuation functions are considered. Indeed, depending on the symbols D = {1, k,∞} and F = {1, h,∞}, nine scenarios MAX-MIN-CSP[D, F] (resp., LEXMAX-MIN-CSP[D, F]) emerge, where the problem is restricted as follows:

• D ∈ {1, k}, with k > 1 being a fixed natural number, stands for the fact that the problem is restricted to sets of formulas L such that maxF∈L |dom(F)| ≤ D. Moreover, D = ∞ means that no restriction is considered on the size of the domains.
• F ∈ {1, h}, with h > 1 being a fixed natural number, stands for the fact that the problem is restricted to sets L such that |L| ≤ h. Moreover, F = ∞means that no restriction is considered on the number of functions.

3 Acyclic CSP Instances

Since solving CSPs-and hence the above extensions-is an NP-hard problem in general, much research has been spent to identify classes of instances over which solutions can efficiently be computed. An approach that is often adopted is to focus on instances (Φ,DB) whose formulas enjoy some desirable "structural" properties. In particular, constraint interactions in Φ can be formalized via the hypergraph H(Φ) = (V,H), where V = Var and where, for each atom occurring in the constraint formula Φ, the set H of hyperedges contains a hyperedge including all its variables. Then, a structural property often considered for such hypergraphs is acyclicity.

A (hyper)graph H is acyclic 3 iff it has a join tree [Bernstein and Goodman, 1981]. A join tree JT (H) for a hypergraph H is a tree whose vertices are the (hyper)edges of H such that, whenever the same node X occurs in two (hyper)edges h1 and h2 of H, then X occurs in each vertex on the unique path linking h1 and h2 in JT(H).

Example 3.1. The hypergraph H(Φ) for the formula Φ in Example 2.1 is reported in Figure 2. Note that H(Φ) is acyclic, as it is witnessed by the join tree reported in the figure. ✁

3.1 Bad News fromAcyclic Instances

It is well-known that acyclic CSP instances, i.e., instances whose associated hypergraphs are acyclic, can be solved in polynomial time (see, e.g., [Gottlob et al., 2000]). Hence, the natural question comes into play about whether this result still holds for MAX-MIN-CSP and LEXMAX-MIN-CSP.

The answer for the case where there is just one valuation function immediately derives from results in the literature. Indeed, in this case, MAX-MIN optimization is immaterial (even in the lexicographic variant) and the setting reduces to standard constraint optimization over acyclic instances.

Theorem 3.2 (see [Gottlob et al., 2009]). On classes of acyclic instances, LEXMAX-MIN-CSP[∞, 1] is in P.

The above tractability result is however tight. Indeed, we next show that intractability emerges in the problem MAXMIN-CSP[∞, 2], which turns out to be weakly-NP-hard.

Theorem 3.3. MAX-MIN-CSP[∞, 2] is weakly-NP-hard, even when restricted to classes of acyclic instances.

Proof Sketch. Given a multi-set S = {s1, s2, ..., sn} of integers, let us build a CSP instance (Φ,DB) over Var = {X1, ...,Xn} ∪ {Y1, ..., Yn} and U = {in, out} as follows. The formula Φ is r(X1, Y1) ∧ ... ∧ r(Xn, Yn), while the database DB precisely contains the two ground atoms r(in, out) and r(out, in). Moreover, consider the valuation functions F1 = 〈w1,+〉 and F2 = 〈w2,+〉 such that dom(F1) = {X1, ...,Xn} and dom(F2) = {Y1, ..., Yn}. In particular, for each si ∈ S, we have w1(Xi/in) = si, w1(Xi/out) = 0, w2(Yi/in) = si, and w2(Yi/out) = 0.

Now, note that MAX-MIN-VAL(Φ,DB, {F1,F2}) = 1 2 ∑ni=1 si holds if and only if we can partition S in two multi-sets S1 and S2 such that the sum of the numbers in S1 equals the sum of those in S2. The result follows as this latter problem is weakly-NP-hard [Garey and Johnson, 1990].

3 Actually, there are different notions of hypergraph acyclicity. We use the most liberal one, known as α-acyclicity [Fagin, 1983].

Note that the above result does not preclude the existence of pseudo-polynomial algorithms for MAX-MIN-CSP[∞, 2]. In fact, we next describe an algorithm for (LEX)MAX-MINCSP whose running time is polynomial when input numbers are taken in unary notation.The result applies to the more general case of instances with any bounded number of functions.

Theorem 3.4. On classes of acyclic instances, LEXMAXMIN-CSP[∞, h] is feasible in pseudo-polynomial time.

Proof Idea. Let (Φ, DB, L) be an acyclic instance, with L = {F1, ...,Fh}. We compute an optimal answer (if any) in pseudo-polynomial time, by using as an oracle the algorithm in [Greco and Scarcello, 2011] that, given an additional vector (v1, .., vh) of real numbers, decides in pseudo-polynomial time whether there is a solution θ ∈ ΦDB with Fi(θ) = vi, for each i ∈ {1, ..., h}. Let us name this algorithm A.

We first check whether ΦDB ̸= ∅ in polynomial time (as H(Φ) is acyclic). If the above check is negative, then we return the empty output and halt. Otherwise, we compute an upper bound of the maximum possible vector of values, by computing the maximum value Mi for each valuation function Fi, ≤ i ≤ h (over the solutions in ΦDB ). This is feasible in polynomial time, by Theorem 3.2. Then, starting from the upper bound vector obtained by non-decreasingly sorting these maximum values, we enumerate (going downward) the pseudo-polynomially many vectors ¯ v = (v1, ..., vh) that may be associated with solutions and, for each of them, we use A to check whether there actually exists some θ ∈ ΦDB such that L(θ) = ¯ v. This way, we identify ¯ v∗ = max{L(θ) | θ ∈ ΦDB}. Then, θ is easily computed by a final loop exploiting standard self-reducibility methods and arguments, again using algorithm A to identify the correct variable assignments leading to the desired vector of values ¯ v∗ .

We leave the section by showing that the "symmetric" scenario is intractable, too-this time in the (usual) strong sense.

Theorem 3.5. MAX-MIN-CSP[2,∞] is NP-hard, even on classes of acyclic instances.

Proof Sketch. Let E = {1, ...,m} be a set of m distinct elements (w.l.o.g., natural numbers), and let S = {s1, ..., sn} be a set of subsets of E. A set packing (for S) is a set S ′ ⊆ S such that si ∩ sj = ∅, for each pair si, sj ∈ S ′ . Computing the set packing having the largest possible cardinality is a well-known NP-hard problem [Garey and Johnson, 1990].

Based on E and S, we define the domain U = {in, out}∪ {to0, to1, to2, ..., ton}∪{0, 1, ..., n} of constants and the set Var = {X1, ..,Xm} ∪ {W0,W1, ...,Wn} ∪ {Yi,e | si ∈ S, e ∈ si} of variables. Moreover, for each set si = {e1, ..., eni } ∈ S where e1 < e2 < ... < eni , we denote by ℓi the list Yi,e1 , ..., Yi,eni , and by ci,in (resp., ci,out) the list consisting of ni repetitions of the constant in (resp., out).

Then, we build the (acyclic) formula Φ such that

and the database DB such that:

• The ground atoms map(to0), ...,map(ton) are in DB;
• For each set si ∈ S and each natural number count ∈ {0, 1, ..., i-1}, the ground atoms select (count , count + 1, ci,in) and select (count , count , ci,out) are in DB;
• No further ground atom is in DB.

Before equipping (Φ,DB) with a set of functions, let us point out the main property of the reduction. A substitution θ : Var ↦→ U is said legal if for each e ∈ E, θ(Xe) = toi holds if, and only if, θ(Yi,e) = in holds. Moreover, let sp(θ) be the set {si ∈ S | θ(Wi) = θ(Wi-1) + 1}. It can be checked that if θ is a legal solution, then sp(θ) is a set packing whose cardinality is θ(Wn). Conversely, if S ′ is a set packing, then there is a legal solution θ with sp(θ) = S ′ .

Now, for each e ∈ E and each set si ∈ S with e ∈ si, we define the functions Fi,e = 〈wi,e,+〉 and ¯ Fi,e = 〈 ¯wi,e,+〉 with dom(Fi,e) = dom( ¯ Fi,e) = {Xe, Yi,e} and such that:

• wi,e(Xe/toj) = n, for each j ̸= i; wi,e(Xe/toi) = 0; wi,e(Yi,e/in) = n; wi,e(Yi,e/out ) = 0.
• ¯wi,e(Xe/toj) = 0, for each j ̸= i; ¯wi,e(Xe/toi) = n; ¯wi,e(Yi,e/in) = 0; ¯wi,e(Yi,e/out) = n.

Consider also the function Fn = 〈wn, +〉 with dom(F) = {Wn} and wn(Wn/i) = i, for each i ∈ {0, 1, ..., n}.

Note that for each solution θ, θ is legal ⇔mini,e Fi,e(θ) = mini,e ¯ Fi,e(θ) > 0 (in fact, n). Hence, MAX-MIN solutions correspond to legal ones. Moreover, let L be the set with all the above functions, and let θ be a legal solution. Then, minF∈L F(θ) = Fn(θ) = θ(Wn) ≤ n. So, θ is a MAX-MIN solution if, and only if, θ is legal and θ(Wn) is the maximum possible value over all legal solutions (hence, the corresponding set packing has the largest possible cardinality).

4 Islands of Tractability

The source of complexity emerged in the above NP-hardness proofs ultimately lies in the interactions that occur between the atoms in Φ and the valuations functions, which are in fact not apparent from the structure of H(Φ). Therefore, the natural question comes into play about whether limiting this interaction can lead to identify islands of tractability.

4.1 Revisiting the Acyclic Case

A positive answer to the above question can be given when the domain of each function is defined over one variable only.

Theorem 4.1. On classes of acyclic instances, LEXMAXMIN-CSP[1,∞] is in P.

Proof Idea. Let (Φ,DB) be an acyclic instance, and let L = {F1, ...,Fm} be a set of valuation functions, where |dom(Fi)| = 1, for each i ∈ {1, ...,m}. Let T be a join tree of H(Φ) (which can be computed in linear time [Gottlob et al., 2001]), and let us root it at an arbitrary vertex r. Recall that each vertex v in T corresponds to a hyperedge of H(Φ) and, hence, (w.l.o.g.) to an atom av in Φ, and define (initially) relv as the set of partial substitutions θv that are in aDB v , i.e., that are solutions to the CSP restricted to the atom av.

Let us fix some notations. For any substitution θ : X ↦→ U, define L↓ (θ) as the projection of the sorted vector L(θ) to the components of those functions F ∈ L with dom(F) ⊆ X. For a set of substitutions S with domain X , we say that θ ∈ S is ≻-maximal in S if L↓ (θ) = max{L↓ (θ′ ) | θ′ ∈ S}.

Moreover, for the vectors of real numbers (v1, ..., vh) and (w1, ...,wk), denote by (v1, ..., vh) ⊙ (w1, ...,wk) the nondecreasingly sorted vector including the components from both vectors. It can be shown that a useful property of this operator is that it distributes over max: If V1 and V2 are two sets of non-decreasingly ordered vectors, then max{¯ v1 ⊙ ¯ v2 | ¯ v1 ∈ V1, v2 ∈ V2} = max V1 ⊙ max V2.

In order to compute a LEXMAX-MIN solution to (Φ,DB) w.r.t. L, we traverse T from the leaves to the root (according to a topological ordering): At each vertex v, for each substitution θv ∈ relv and for each child c of v in T, we focus on those substitutions ¯ θc in relc that conform with θv, denoted by θv ≈ ¯ θc, that is, for each variable X that the domains of ¯ θc and θv have in common, it must be the case that ¯ θc(X) = θv(X). If there is no substitution in relc conforming with θv, then we conclude that θv cannot be extended to a solution in ΦDB and it is removed from relv. Otherwise, θv is enlarged by adding to it any ≻-maximal substitution θc in the set of substitutions from rel c conforming with θv. Note that

Eventually, when the root r is reached, any substitution ≻- maximal in relr is returned as the output.

It is easy to see that the proposed algorithm runs in polynomial time. The formal proof of correctness is based on a structural induction over the join tree T, whose underlying idea is the following. Consider a vertex v and a substitution θv ∈ rel v, and assume inductively that, for each child ci of v, each substitution θi ∈ rel ci is an optimal one for the problem induced by the variables occurring in the subtree of T rooted at ci, and where the variables occurring in ci are fixed according to θi. Recall that T is a join tree and thus the domains of the substitutions in the children of v can overlap only on the variables they have in common with v. Therefore, the same holds for the unary valuation functions. Then, by Eq. (1) and the fact that ⊙ distributes over max, the composition of θv with the best substitutions conforming with θv over all the children of v in T provides the best solution for the larger subproblem including the variables occurring in the atom associated with v, fixed according to θv. After this step, relv contains one best partial substitution for the subtree rooted at v, for each partial substitution for the variables in v.

4.2 Guards and Tractable Acyclic Instances

Our goal is now to generalize the above result, by defining some specific notion of LEXMAX-MIN CSP structure where such interactions are considered and exploited in a suitable way, in order to identify larger islands of tractability.

The first step is to take under control the variables in the domain of valuation functions. To this end, we adopt a method inspired by the characterization of acyclic instances in terms of guarded formulas, that is, the fragment of positive existential first-order queries where the free variables of every subformula occur together in some atom, called its guard.

Let H = (V,H) be a hypergraph, and let W and {X, Y } be sets of nodes. A [W]-path fromX to Y is a sequence X = X0, . . . , Xℓ = Y of nodes such that, for each i ∈ {0, ..., ℓ-1}, {XiXi+1} ⊆ (hi \ W), for some hyperedge hi ∈ H. We say that C is [W]-connected if ∀X, Y ∈ C there is a

[W]-path from X to Y . A [W]-component (of H) is a maximal [W]-connected non-empty set of nodes C ⊆ (V \W).

Definition 4.2. Let Φ be a constraint formula, let L be a set of valuation functions, and let F ∈ L. A set W of nodes of H(Φ) (i.e., variables in Φ) is a guard for F (w.r.t. L) if every [W]-component C of H(Φ) with C ∩ dom(F) ̸= ∅ is such that C ∩ dom(F ′ ) = ∅, for each F ′ ∈ L with F ′ ̸= F. ✷

Intuitively, a guard W for F may directly cover some variables of dom(F), which will not appear in any [W]-component, and separates the remaining variables from the variables occurring in the other valuation functions.

Example 4.3. Consider the (hyper)graph H(Φ) shown in Figure 3 (by assuming, for simplicity, that variables have numerical domains), and the valuation functions F1,F2, and F3 such that F1(θ) = θ(X1) + θ(X4) + θ(X8), F2(θ) = θ(X2) × θ(X5), and F3(θ) = 5 × θ(X3). In this example, the set {X1,X2,X3} is a guard for Fi, ∀i ∈ {1, 2, 3}. ✁

The second step is to deal with the intricacy of the CSP, measured in terms of "degree of cyclicity" of the associated hypergraph. In fact, we next provide tractability results for LEXMAX-MIN-CSP[∞,∞] over classes that are strictly more general than those considered in the previous section. To this end, recall (see, e.g., [Gottlob et al., 2000]) that a structural decomposition method Ψ can be viewed as a function associating each CSP instance (Φ,DB) with a set Ψ(Φ,DB) of equivalent acyclic CSP instances, that is, ¯Φ ¯ DB = ΦDB , for each (¯Φ, ¯ DB) ∈ Ψ(Φ, DB).

Definition 4.4. Let Ψ be a structural decomposition method and let I = (Φ,DB,L) be an instance of (LEX)MAX-MINCSP. A CSP instance (¯Φ, ¯ DB) ∈ Ψ(Φ,DB) is a [Ψ,L]- decomposition (of I) if, for each F ∈ L, there is a hyperedge W of H(¯Φ) that is a guard for F. Whenever such a decomposition exists, we say that I is guarded via Ψ. ✷

As a "baseline" method, let Ψa be the acyclic method returning the instance itself when this is acyclic, and ∅ otherwise. Then, the following is immediate by Definition 4.4.

Fact 4.5. Let I be any acyclic LEXMAX-MIN-CSP[D, F] instance, with D = 1 or F = 1. Then, I is guarded via Ψa.

Therefore, Theorem 4.1 can be seen now as singling out a class of guarded tractable instances. We next generalize this result to more powerful structural methods (using Theorem 4.1 as a technical tool), by showing that guardedness is sufficient to ensure tractability without any further restriction.

Theorem 4.6. Given any instance (Φ, DB, L) with a [Ψ, L]- decomposition, a solution of LEXMAX-MIN-CSP (if any) can be computed in polynomial time.

Proof Idea. Let (¯Φ, ¯ DB) be the given [Ψ,L]-decomposition of (Φ,DB,L), with L = {F1, ...,Fm}. We build in polynomial time an instance (Φ′ ,DB′ ,L′ ) as follows. For each function Fi, 1 ≤ i ≤ m, chose one atom ri(ui) of ¯Φ such that its variables are a guard for Fi. Such an atom exists by definition of [Ψ,L]-decomposition. The constraint formula Φ′ is the same as ¯Φ but, for each each Fi, 1 ≤ i ≤ m, it contains a fresh atom r′i (ui, Xi) having the same terms as the guard ri plus an additional fresh variable Xi. Correspondingly, DB′ is the same as ¯ DB but, for each i ∈ {1, ...,m} and partial substitution θ such that ri(θ(ui)) ∈ ¯ DB, we have the ground atom r′i (θ(ui), v∗ θ ) in DB′ , where v∗ θ is the optimal value of the LEXMAX-MIN-CSP[∞, 1] (acyclic) CSP instance (¯Φ, ¯ DB) equipped only with function Fi and where the variables in ui are fixed to θ(ui). Note that these values, which form the domain of variable Xi in the new instance, can be computed in polynomial time by Theorem 3.2. Finally, let L′ = {F ′1 , ..., F ′m}, where F ′ i = (wi,+), 1 ≤ i ≤m, is a unary function with dom(F ′ i ) = Xi and wi(Xi/c) = c.

Note that new instance is acyclic, too. Moreover, (Φ′ ,DB′ ,L′ ) and (Φ,DB,L) are equivalent since, by the guardedness, the substitutions of Xi stored in the ground atoms of DB′ encode all possible values of F ′ i that may be associated with solutions of ΦDB . The result then follows as (Φ′ , DB′ , L′ ) can be solved in P, by Theorem 4.1.

Well-known decompositions methods that are tractable, in that any of their output instances may be computed in polynomial time, are the bounded treewidth (tw) [Robertson and Seymour, 1984] and the bounded hypertree width (htw) methods [Gottlob et al., 2002]. Let k be any fixed natural number, representing intuitively the maximum degree of cyclicity we want to deal with. Then, Ψtw-k returns the set of all equivalent acyclic instances where each atom contains k -1 variables at most, while Ψhw-k returns the set of all the equivalent acyclic instances whose hypergraphs are width-k hypertree decompositions in normal form of the given instance. Basically, in Ψhw-k, we consider instances whose atoms are subproblems comprising at most k constraints of the original instance. We refer the interested reader to [Gottlob et al., 2002], for further background on Ψhw-k.

Example 4.7. Consider again Figure 3. The acyclic instance whose hypergraph comprises the hyperedge {X1, X2, X3} is a [Ψtw-2, L]-decomposition, as the additional hyperedge uses 2 + 1 variables and is a guard for the functions. In fact, it is also a [Ψhtw-2, L]-decomposition, as the set {X1,X2,X3} can be covered by 2 (binary) original constraints. ✁

As a further example, we point out that the case of acyclic instances with a bounded number of valuation functions with bounded domains is generalized by the class of guarded bounded hypertree-width instances. This can be shown by noticing that h×k variables (hence, constraints) are sufficient to cover the union of all the domains of the given functions.

Fact 4.8. Let I be any acyclic LEXMAX-MIN-CSP[h, k] instance. Then, I is guarded via Ψhw-(h×k+1).

Turning to computational aspects, we observe that while computing an arbitrary decomposition according to the above methods is tractable, in order to solve (LEX)MAX-MINCSP instances, we should be able to filter, out of exponentially many possible candidates, a decomposition with all the guards needed to take care of the valuation functions. Of course, a na¨ıve enumeration approach is not feasible here, and a more involved approach is needed to get tractability.

Theorem 4.9. Deciding whether an instance is guarded via Ψtw-k (resp., Ψhw-k) is feasible in polynomial time.

Proof Idea. We consider the more general case of Ψhw-k. We use the notion of weighted hypertree decompositions [Scarcello et al., 2007], with a suitable function ξ weighing any normal form width-k decomposition, usually represented through a labeled join tree, called decomposition tree. The function ξ is such that, whenever an optimal decomposition has -|L| as its (minimum) weight, the given instance is guarded via Ψhw-k. Moreover, such an optimal decomposition can be computed in polynomial time. The first key property is that the subset of variables that are possible candidates to be guards in such decompositions can be enumerated in polynomial time. The second property is that, whenever an instance is guarded, for each function F ∈ L, there must be a guard p for F in the decomposition tree such that its subtree rooted at p covers some variable occurring in dom(F ′ ) \ dom(F), for some (other) function F ′ ∈ L. Then, the weighing function ξ assigns a weight -1 to such a vertex p (more precisely, -1 for each function for which p may play this role). From the latter property and the definition of guards, it can be seen that at most one guard for each valuation function may get weight -1 in any hypertree decomposition. Hence, decompositions having total weight -|L| must have a guard for each valuation function.

An easy consequence is the desired islands of tractability.

Corollary 4.10. On classes of instances that are guarded via Ψhw-k (and hence via Ψtw-k), solving LEXMAX-MINCSP[∞,∞] is feasible in polynomial time.

5 Conclusion

In this paper, we have described a framework for "fair" CSP optimization, and we have provided a clear picture of the tractability frontier for (LEX)MAX-MIN-CSP[D, F] over acyclic instances, as summarized in Table 1 (where note that hardness results hold even over MAX-MIN-CSP[D, F]). Moreover, we have identified larger classes of tractable instances based on a new structural decomposition approach, which is able to deal with the interactions among the constraints and the valuation functions to be optimized. This is accomplished via a suitable notion of guard of a function that is able to separate its variables from the domains of the other functions, in any decomposition of the (possibly cyclic) given instance. By Fact 4.5 and Fact 4.8, tractable results for acyclic instances are just special cases of such guarded classes.