11institutetext:  Oxford University, University of Calabria
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

# Tractable Optimization Problems through
Hypergraph-Based Structural Restrictions††thanks: G.Gottlob works at the
Computing Laboratory and at the Oxford Man Institute of Quantitative Finance,
Oxford University. This work was done in the context of the EPSRC grant
EP/G055114/1 “Constraint Satisfaction for Configuration: Logical
Fundamentals,Algorithms, and Complexity” and of Gottlob’s Royal Society
Wolfson Research Merit Award.

Georg Gottlob 11 Gianluigi Greco 22 Francesco Scarcello 221122

###### Abstract

Several variants of the Constraint Satisfaction Problem have been proposed and
investigated in the literature for modelling those scenarios where solutions
are associated with some given costs. Within these frameworks computing an
optimal solution is an NP-hard problem in general; yet, when restricted over
classes of instances whose constraint interactions can be modelled via
(nearly-)acyclic graphs, this problem is known to be solvable in polynomial
time. In this paper, larger classes of tractable instances are singled out, by
discussing solution approaches based on exploiting hypergraph acyclicity and,
more generally, structural decomposition methods, such as (hyper)tree
decompositions.

##  1 Introduction

The Constraint Satisfaction Problem (CSP) is a well-known framework [11] for
modelling and solving search problems, which received considerably attention
in the literature due to its applicability in various areas. Informally, a CSP
instance is defined by singling out the variables of interest, and by listing
the allowed combinations of values for groups of them, according to the
constraints arising in the application at hand. The solutions for this
instance are the assignments of domain values to variables that satisfy all
such constraints. Many apparently unrelated problems from disparate areas
actually turn out to be equivalent to the CSP and can be accommodated within
the CSP framework. Examples are puzzles, conjunctive queries over relational
databases, graph colorability, and checking whether there is a homomorphism
between two finite structures.

###### Example 1

Figure 1 shows a combinatorial crossword puzzle (taken from [15]). A set of
legal words is associated with each horizontal or vertical array of white
boxes delimited by black boxes. A solution to the puzzle is an assignment of a
letter to each white box such that to each white array is assigned a word from
its set of legal words. This problem can be recast in a CSP by associating a
variable with each white box, and by defining a constraint for each array of
white boxes prescribing the legal words that are associated with it. $\lhd$

When assignments are associated with some given cost, however, computing an
arbitrary solution might not be enough. For instance, the crossword puzzle in
Figure 1 may admit more than one solution, and expert solvers may be asked to
single out the most difficult ones, such as those solutions that minimize the
total number of vowels occurring in the used words. In these cases, one is
usually interested in the corresponding _optimization problem_ of computing
the solution of minimum cost, whose modeling is accounted for in several
variants of the basic CSP framework, such as fuzzy, probabilistic, weighted,
lexicographic, valued, and semiring-based CSPs (see [25, 4] and the references
therein).

Figure 1: A crossword puzzle, its associated hypergraph ${\cal H}_{cp}$, and a
hypertree decomposition of width 2 for ${\cal H}_{cp}$.

Since solving CSPs—and the above extensions—is an NP-hard problem, much
research has been spent to identify restricted classes over which solutions
can efficiently be computed. In this paper, structural decomposition methods
are considered [15], which identify tractable classes by exploiting the
structure of constraint scopes as it can be formalized either as a hypergraph
(whose nodes correspond to the variables and where each group of variables
occurring in some constraint induce a hyperedge) or as a suitable binary
encoding of such hypergraph. In particular, we focus on the structural methods
based on the notions of (generalized) hypertree width [18, 19] and treewidth
[28]. In both cases, the underlying idea is that solutions to CSP instances
that are associated with acyclic (or nearly-acyclic) structures can
efficiently be computed via dynamic programming, by incrementally processing
the structure according to some of its topological orderings.

As a matter of fact, however, while in the case of classical CSPs deep and
useful results have been achieved for both graph and hypergraph
representations, in the case of CSP extensions tailored for optimization
problems attention was mainly focused on binary encodings and, in particular,
on the _primal graph_ representation, where nodes correspond to variables and
an edge between two variables indicates that they are related by some
constraint. Discussing whether (and how) hypergraph-based structural
decomposition techniques in the literature can be lifted to such optimization
frameworks is the main goal of this paper. In particular, we consider three
CSP extensions:

(1)

First, we consider optimization problems where every mapping variable-value is
associated with a cost, so that the aim is to find an assignment satisfying
all the constraints and having the minimum total cost.

(2)

Second, we consider the case where costs are associated with the allowed
combinations of simultaneous values for the variables occurring in the
constraint, rather than to individual values. Again, within this setting, we
consider the problem of computing a solution having minimum total cost.

(3)

Finally, we consider a scenario where the CSP instance at hand might not admit
a solution at all, and where the problem is hence to find the assignment
minimizing the total number of violated constraints (and, more generally,
whenever a cost is assigned to each constraint, the assignment minimizing the
total cost of violated constraints).

For each of the above settings, the complexity of computing the optimal
solution is analyzed in this paper, by overviewing some relevant recent
research and by providing novel results. In particular:

  * $\blacktriangleright$

We show that optimization problems of kind (1) can be solved in polynomial
time on instances having bounded (generalized) hypertree-width hypergraphs.
This result is based on an algorithm recently designed and analyzed in the
context of _combinatorial auctions_ [13].

  * $\blacktriangleright$

We show that even optimization problems of kind (2) are tractable on instances
having bounded (generalized) hypertree-width hypergraphs. Indeed, we describe
how to transform this kind of instances into equivalent instances of kind (1),
by preserving their structural properties.

  * $\blacktriangleright$

We observe that optimization problems of kind (3) remain NP-hard even over
instances having an associated acyclic hypergraph. However, there is also good
news: they are shown to be tractable on instances having bounded treewidth
incidence graph encoding. The latter is a binary encoding of the constraint
hypergraph with usually better structural features than the primal graph
encoding (see, e.g., [15, 22]). Again, proof is via a mapping to case (1).

Organization. The rest of the paper is organized as follows. Section 2
discusses preliminaries on CSPs and structural restrictions, and Section 3
provides an overview of the structural decomposition methods based on
treewidth and (generalized) hypertree width. Results for optimization problems
of kind (1) and (2) are discussed in Section 4, whereas problems of kind (3)
are discussed in Section 5. Finally, Section 6 draws our conclusions.

##  2 CSPs, Acyclic Instances, and their Desirable Properties

An instance of a constraint satisfaction problem [11] is a triple
$\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$, where ${\it Var}$ is a
finite set of variables, $U$ is a finite domain of values, and
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{q}\\}$ is a finite set of constraints.
Each constraint $C_{v}$, for $1\leq v\leq q$, is a pair $(S_{v},r_{v})$, where
$S_{v}\subseteq{\it Var}$ is a set of variables called the constraint scope,
and $r_{v}$ is a set of substitutions (also called _tuples_) from variables in
$S_{v}$ to values in $U$ indicating the allowed combinations of simultaneous
values for the variables in $S_{v}$. Any substitution from a set of variables
$V\subseteq{\it Var}$ to $U$ is extensively denoted as the set of pairs of the
form $X/u$, where $u\in U$ is the value to which $X\in V$ is mapped. Then, a
solution to $\mathcal{I}$ is a substitution $\theta:{\it Var}\mapsto U$ for
which $q$-tuples $t_{1}\in r_{1},...,t_{q}\in r_{q}$ exist such that
$\theta=t_{1}\cup...\cup t_{q}$.

###### Example 2

In the crossword puzzle of Figure 1, $\it Var$ coincides with the letters of
the alphabet, and a variable $X_{i}$ (denoted by its index $i$) is associated
with each white box. An example of constraint is
$C_{1H}=((1,2,3,4,5),r_{1H})$, and a possible instance for $r_{1H}$ is
$\\{\langle h,o,u,s,e\rangle,\langle c,o,i,n,s\rangle,\langle
b,l,o,c,k\rangle\\}$—in the various constraint names, subscripts $H$ and $V$
stand for “Horizontal” and “Vertical,” respectively, resembling the usual
naming of definitions in crossword puzzles. $\lhd$

The structure of a CSP instance $\mathcal{I}$ is best represented by its
associated hypergraph ${\cal H}(\mathcal{I})=(V,H)$, where $V={\it Var}$ and
$H=\\{S\mid(S,r)\in{\mathcal{C}}\\}$—in the following, $V$ and $H$ will be
denoted by ${\mathcal{N}}({\cal H})$ and ${\mathcal{E}}({\cal H})$,
respectively. As an example, the hypergraph associated with the crossword
puzzle formalized above is illustrated in the central part of Figure 1.

A hypergraph ${\cal H}$ is acyclic iff it has a join tree [3]. A join tree
$J\\!T({\cal H})$ for a hypergraph ${\cal H}$ is a tree whose vertices are the
hyperedges of ${\cal H}$ such that, whenever the same node $X\in V$ occurs in
two hyperedges $h_{1}$ and $h_{2}$ of ${\cal H}$, then $X$ occurs in each
vertex on the unique path linking $h_{1}$ and $h_{2}$ in $J\\!T({\cal H})$.
The notion of acyclicity we use here is the most general one known in the
literature, coinciding with $\alpha$-acyclicity according to Fagin [9]. Note
that the hypergraph ${\cal H}_{cp}$ of Figure 1 is not acyclic. An acyclic
hypergraph is discussed below.

Figure 2: A hypergraph ${\cal H}_{1}$, a join tree $J\\!T({\cal H}_{1})$, the
primal graph ${\it G}({\cal H}_{1}$), and the incidence graph ${\it inc}({\cal
H}_{1})$.

###### Example 3

Consider the hypergraph ${\cal H}_{1}$ shown on the left of Figure 2, which is
associated with a CSP instance over the set of variables $\\{A,...,M\\}$. In
particular, six constraints are defined over the instance whose scopes
precisely correspond to the hyperedges in ${\mathcal{E}}({\cal H}_{1})$; for
instance, $\\{A,B,C\\}$ is an example of constraint scope. Note also that
${\cal H}_{1}$ is acyclic. Indeed, a join tree $J\\!T({\cal H}_{1})$ for it is
reported in the same figure to the right of ${\cal H}_{1}$. $\lhd$

An important property of acyclic instances is that they can efficiently be
processed by dynamic programming. Indeed, according to Yannakakis’ algorithm
[34] (originally conceived in the equivalent context of evaluating acyclic
Boolean conjunctive queries), they can be evaluated by processing any of their
join trees bottom-up, by performing upward semijoins between the constraint
relations, thus keeping the size of the intermediate result small. At the end,
if the constraint relation associated with the root atom of the join tree is
not empty, then the CSP instance does admit a solution. Therefore, the whole
procedure is feasible in $O(n\times r_{max}\times\log r_{max})$, where $n$ is
the number of constraints and $r_{max}$ denotes the size of the largest
constraint relation.

In addition to the polynomial time algorithm for deciding whether a CSP admits
a solution, acyclic instances enjoy further desirable properties:

Acyclicity is efficiently recognizable:

Deciding whether a hypergraph is acyclic is feasible in linear time [31] and
belongs to the class ${\rm L}$ (deterministic logspace). Indeed, this follows
from the fact that hypergraph acyclicity belongs to SL [16], and that SL is
equal to ${\rm L}$ [27].

Acyclic instances can be efficiently solved:

After the bottom-up step described above, one can perform the reverse top-down
step by filtering each child vertex from those tuples that do not match with
its parent tuples. The relations obtained after the top-down step enjoy the
global consistency property, i.e., they contain only tuples whose values are
part of some solution of the CSP. Then, all solutions can be computed with a
backtrack-free procedure, and thus in total polynomial time, i.e., in time
polynomial in the input plus the output [34] (and actually also with
polynomial delay). Alternatively, one may enforce pairwise consistency by
taking the semijoins between all pairs of relations until a fixpoint is
reached. Indeed, acyclic instances that fulfil this property also fulfil the
global consistency property [2].

Acyclic instances are parallelizable:

It has been shown that solving acyclic CSP instances is highly parallelizable,
as this problem (actually, deciding the existence of a solution) is complete
for the low complexity class LOGCFL [16]. Efficient parallel algorithms are
discussed in [16] and [17].

We conclude this section by recalling that the above desirable properties of
acyclic CSP instances have profitably been exploited in various application
scenarios. Indeed, besides their application in the context of Database
Theory, they found applications in Game Theory [14, 8], Knowledge
Representation and Reasoning [21], and Electronic Commerce [13], just to name
a few.

##  3 Generalizing acyclicity

Many attempts have been made in the literature for extending the good results
about acyclic instances to relevant classes of nearly acyclic structures. We
call these techniques structural decomposition methods, because they are based
on the “acyclicization” of cyclic (hyper)graphs. We refer the interested
reader to [29] for a detailed description of how these techniques may be
useful for constraint satisfaction problems and to [22] for further results
about graph-based techniques, when relational structures are represented
according to various graph representations (primal graph, dual graph,
incidence-graph encoding). We also want to mention recent methods such as
Spread-cuts [7] and fractional hypertree decompositions [23].

A survey of most of these techniques is currently available in Wikipedia (look
for “decomposition method”, at http://www.wikipedia.org). In the sequel, we
shall briefly overview the tree and hypertree decomposition methods.

###  3.1 Tree Decompositions

For classes of instances having only binary constraints or, more generally,
constraints whose scopes have a fixed maximum arity, the most powerful
structural method is based on the notion of treewidth.

######  Definition 1 ([28])

A tree decomposition of a graph $G=(V,E)$ is a pair $\langle T,\chi\rangle$,
where $T=(N,F)$ is a tree, and $\chi$ is a labelling function assigning with
each vertex $p\in N$ a set of vertices $\chi(p)\subseteq V$ such that the
following conditions are satisfied: (1) for each node $b$ of $G$, there exists
$p\in N$ such that $b\in\chi(p)$; (2) for each edge $(b,d)\in E$, there exists
$p\in N$ such that $\\{b,d\\}\subseteq\chi(p)$; and, (3) for each node $b$ of
$G$, the set $\\{p\in N\mid b\in\chi(p)\\}$ induces a connected subtree of $T$
(_connectedness condition_). The width of $\langle T,\chi\rangle$ is the
number $\max_{p\in N}(|\chi(p)|-1)$. The treewidth of $G$, denoted by $tw(G)$,
is the minimum width over all its tree decompositions. $\Box$

It is well-known that a graph $G$ is acyclic if and only if $tw(G)=1$.
Moreover, for any fixed natural number $k>0$, deciding whether $tw(G)\leq k$
is feasible in linear time [5].

Any CSP with primal graph $G$ such that $tw(G)\leq k$ can be (efficiently)
turned into an equivalent CSP whose primal graph is acyclic. Let
$\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$ be a CSP instance, let $G$
be the primal graph of ${\cal H}(\mathcal{I})$, and let $\langle
T,\chi\rangle$ be a tree decomposition of $G$ having width $k$. We may build a
new acyclic CSP instance $\mathcal{I}^{\prime}=\langle{\it
Var},U,\mathcal{C}^{\prime}\rangle$ over the same variables and universe as
$\mathcal{I}$, but with a different set of constraints $\mathcal{C}^{\prime}$,
as follows. Firstly, for each vertex $v$ of $T$, we create a constraint
$(S_{v},r_{v})$, where $S_{v}=\chi(v)$ and $r_{v}=U^{|\chi(v)|}$. Then, for
every constraint $(S,r)\in\mathcal{C}$ of the original problem such that
$S\subseteq\chi(v)$, we eliminate from $r_{v}$ all those tuples that do not
match with $r$. The resulting constraint is then added to
$\mathcal{C}^{\prime}$. It can be shown that $\mathcal{I}^{\prime}$ has the
same solutions as $\mathcal{I}$, and that it is acyclic. In fact, observe
that, by construction, $\langle T,\chi\rangle$ is a join tree of the
hypergraph ${\cal H}(\mathcal{I}^{\prime})$ associated with
$\mathcal{I}^{\prime}$, because of the connectedness condition of tree
decompositions. Furthermore, building $\mathcal{I}^{\prime}$ from
$\mathcal{I}$ is feasible in $O(n\times|U|^{k+1})$ where $n$ is the number of
vertices in $T$, and where the size of the largest constraint relation in the
resulting instance is $|U|^{k+1}$. Since one can always consider only tree
decompositions whose number of vertices is bounded by the number of variables
of the problem (i.e., the nodes of the graph), it follows that deciding
whether $\mathcal{I}^{\prime}$ (and hence $\mathcal{I}$) is satisfiable is
feasible in $O(|Var|\times|U|^{k+1}\times\log|U|^{k+1})$. In fact, as for
acyclic instances, even in this case we may compute also solutions for
$\mathcal{I}$ with a backtrack-free search, after the preprocessing of the
instance performed according to the given tree decomposition (i.e., according
to the join tree of the equivalent acyclic instance). As a consequence, all
classes of CSP instances (with primal graphs) having bounded treewidth may be
solved in polynomial time, even if with an exponential dependency on the
treewidth.

Clearly enough, this technique is not very useful for CSP instances with large
constraint scopes. In particular, the class of CSP instances whose associated
constraint hypergraphs are acyclic are not tractable according to tree
decompositions, because acyclic hypergraphs may have unbounded treewidth.
Intuitively, in the primal graph all variables occurring in the same
constraint scope are connected to each other, and thus they lead to a clique
in the graph. It follows that CSP instances having constraint scopes with
large arities have large treewidths, too, because the treewidth of a clique of
$n$ nodes is $n-1$. As an example, Figure 2 reports the graph ${\it G}({\cal
H}_{1})$ associated with the acyclic hypergraph ${\cal H}_{1}$, where one may
notice how the hyperedge $\\{A,C,D,E,F,G,H\\}$ is flattened into a clique over
all its variables.

###  3.2 Hypertree Decompositions

Let us now turn our attention to hypergraph based decompositions. Such
decompositions are similar to tree decompositions, but they use an additional
covering of each set $\chi(p)$ with as few as possible hyperedges. The width
is then no longer defined as the maximum cardinality of $\chi(p)$ over all
decomposition nodes $p$, but as the maximum number of hyperedges used to cover
$\chi(p)$. Intuitively, this notion of width is better, because it will allow
us to expresses more accurately the computational effort needed to transform
an instance into an acyclic one.

######  Definition 2 ([19])

A generalized hypertree decomposition of a hypergraph ${\cal H}$ is a triple
$H\\!D=\langle T,\chi,\lambda\rangle$, where $\langle T,\chi\rangle$ is a tree
decomposition of the primal graph of ${\cal H}$, and $\lambda$ is a labelling
of the tree $T$ by sets of hyperedges of ${\cal H}$ such that, for each vertex
$p\in vertices(T)$, $\chi(p)\subseteq\bigcup_{h\in\lambda(v)}h$. That is, all
variables in the $\chi$ labeling are covered by hyperedges (scopes) in the
$\lambda$ labeling. The width of $H\\!D$ is the number $\max_{p\in
vertices(T)}(|\lambda(p)|)$. The generalized hypertree width of ${\cal H}$,
denoted by $ghw({\cal H})$, is the minimum width over all its generalized
hypertree decompositions. If $I$ is a CSP instance then $ghw(I):=ghw({{\cal
H}}(I))$. $\Box$

Clearly, for each CSP instance $I$, $ghw(I)\leq tw(I)$. Moreover, there are
classes of CSPs having unbounded treewidth whose generalized hypertree width
is bounded[19].

Finding a suitable tree decomposition whose sets $\chi(p)$ may each be covered
with a few hyperedges seems to be quite a hard task even in case we have some
fixed upper bound $k$. Indeed, it has been shown that deciding whether
$ghw({\cal H})\leq k$ is NP-complete (for any fixed $k\geq 3$) [20].
Fortunately, since its first proposal in [18], this notion comes with a
tractable variant, called hypertree decomposition, whose associated width is
at most 3 times (+1) larger than the generalized hypertree width [1]. As a
consequence, it can be shown that every class of CSPs that is tractable
according to generalized hypertree width is tractable according to hypertree
width, as well.

######  Definition 3 ([18])

A hypertree decomposition of a hypergraph ${\cal H}$ is a generalized
hypertree decomposition $H\\!D=\langle T,\chi,\lambda\rangle$ that satisfies
the following additional condition, called Descendant Condition or also
special condition: $\forall p\in vertices(T)$, $\forall h\in\lambda(p)$,
$h\cap\chi(T_{p})\;\subseteq\;\chi(p)$, where $T_{p}$ denotes the subtree of
$T$ rooted at $p$, and $\chi(T_{p})$ the set of all variables occurring in the
$\chi$ labeling of this subtree.

The hypertree width $hw({\cal H})$ of ${\cal H}$ is the minimum width over all
its hypertree decompositions. $\Box$

As an example, on the right part of Figure 1 a hypertree decomposition of the
hypergraph ${\cal H}_{cp}$ in Example 1 is reported. Note that this
decomposition has width 2.

We refer the interested reader to [18, 29] for more details about this notion
and in particular about the descendant condition. Here, we just observe that
the notions of hypertree width and generalized hypertree width are true
generalizations of acyclicity, as the acyclic hypergraphs are precisely those
hypergraphs having hypertree width and generalized hypertree width one. In
particular, the classes of CSP instances having bounded (generalized)
hypertree width have the same desirable computational properties as acyclic
CSPs [16]. Indeed, from a CSP instance $\mathcal{I}=\langle{\it
Var},U,\mathcal{C}\rangle$ and a (generalized) hypertree decomposition $H\\!D$
of ${\cal H}(\mathcal{I})$ of width $k$, we may build an acyclic CSP instance
$\mathcal{I}^{\prime}=\langle{\it Var},U,\mathcal{C}^{\prime}\rangle$ with the
same solutions as $\mathcal{I}$. The overall cost of deciding whether
$\mathcal{I}$ is satisfiable is in this case $O((m-1)\times
r_{max}^{k}\times\log r_{max}^{k})$, where $r_{max}$ denotes the size of the
largest constraint relation and $m$ is the number of vertices of the
decomposition tree, with $m\leq|{\it Var}|$ (in that we may always find
decompositions in a suitable normal form without redundancies, so that the
number of vertices in the tree cannot exceed the number of variables of the
given instance). To be complete, if the input consists of $\mathcal{I}$ only,
we have to compute the decomposition, too. This can be done with a guaranteed
polynomial-time upper bound in the case of hypertree decompositions [18].

In the following two sections, we provide some tractability results for
optimization problems. For the sake of presentation, we give algorithms for
the acyclic case, provided that these results may be clearly extended to any
class of instances having bounded (generalized) hypertree width, after the
above mentioned polynomial-time transformation.

##  4 Optimization Problems over CSP Solutions

In this section, we consider optimization problems where an assignment has to
be singled out that satisfies all the constraints of the underlying CSP
instance and that has minimum total cost; in other words, we look for a “best”
solution among all the possible solutions. In particular, below, we shall
firstly address the case where each possible variable-value mapping is
associated with a cost (also called constraint satisfaction optimization
problem); then we shall consider the case where costs are defined over the
constraints tuples (weighted CSP).

###  4.1 Constraint Satisfaction Optimization Problems

An instance of a constraint satisfaction optimization problem (CSOP) consists
of a pair $\langle\mathcal{I},{w}\rangle$, where $\mathcal{I}=\langle{\it
Var},U,\mathcal{C}\rangle$ is a CSP instance and where ${w}:{\it Var}\times
U\mapsto\mathbb{Q}$ is a function mapping substitutions for individual
variables to rational numbers. For a substitution
$\\{X_{1}/u_{1},...,X_{n}/u_{n}\\}$, we denote by
${w}(\\{X_{1}/u_{1},...,X_{n}/u_{n}\\})$ the value
$\sum_{i=1}^{n}{w}(X_{i},u_{i})$. Then, a solution to a CSOP instance
$\langle\mathcal{I},{w}\rangle$ is a solution $\theta$ to $\mathcal{I}$ such
that ${w}(\theta)\leq{w}(\theta^{\prime})$, for each solution
$\theta^{\prime}$ to $\mathcal{I}$. Details on this framework can be found,
e.g., in [32].

Input: An acyclic CSOP instance $\langle\mathcal{I},{w}\rangle$ with
$\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$,
$\mathcal{C}=\\{(S_{1},r_{1}),...,(S_{q},r_{q})\\}$, and a join tree $T=(N,E)$
of the hypergraph ${\cal H}(\mathcal{I})$; Output: A solution to
$\langle\mathcal{I},{w}\rangle$; var ${t}^{*}:{\it Var}\mapsto U$;
$\ell_{{{t}_{v}}}^{v}:\mbox{rational number, for each tuple }{t}_{v}\in
r_{v}$; ${t}_{{t}_{v},c}:\mbox{tuple in }r_{c}$, for each tuple ${t}_{v}\in
r_{v}$, and for each $(v,c)\in E$; ————————————————————————————————————————–
Procedure $BottomUp$; begin $Done:=$ the set of all the leaves of $T$; while
$\exists v\in T$ such that (i) $v\not\in Done$, and (ii) $\\{c\mid c\mbox{ is
child of }v\\}\subseteq Done$ do $r_{v}:=r_{v}-\\{{t}_{v}\mid\exists(v,c)\in
E\mbox{ such that }\forall{t}_{c}\in\theta_{c},\ {t}_{v}\not\approx\
{t}_{c}\\}$; if $r_{v}=\emptyset$ then EXIT; (* $\mathcal{I}$ is not
satisfiable *) for each ${t}_{v}\in r_{v}$ do
$\ell_{{t}_{v}}^{v}:=w({t}_{v})$; for each $c$ such that $(v,c)\in E$ do
$\bar{t}_{c}:=\arg\min_{{t}_{c}\in r_{c}\mid{t}_{v}\approx\
{t}_{c}}\left(\ell_{{t}_{c}}^{c}-w({t}_{c}\cap{t}_{v})\right);$
${t}_{{t}_{v},c}:=\bar{t}_{c}$; (* set best solution *)
$\ell_{{t}_{v}}^{v}:=\ell_{{t}_{v}}^{v}+\ell_{\bar{t}_{c}}^{c}-w(\bar{t}_{c}\cap{t}_{v})$;
end for end for $Done:=Done\cup\\{v\\}$; end while end;
————————————————————————————————————————– begin (* MAIN *) $BottomUp$; let $r$
be the root of $T$; $\bar{t}_{r}:=\arg\min_{{t}_{r}\in
r_{r}}\ell_{{t}_{r}}^{r}$; ${t}^{*}:=\bar{t}_{r}$; (* include solution *)
$TopDown(r,\bar{t}_{r})$; return ${t}^{*}$; end. Procedure
$TopDown(v:\mbox{vertex of }N$, ${t}_{v}\in r_{v}$); begin for each $c\in N$
s.t. $(v,c)\in E$ do $\bar{t}_{c}:={t}_{{t}_{v},c}$;
${t}^{*}:={t}^{*}\cup\bar{t}_{c}$; (* include solution *)
$TopDown(c,\bar{t}_{c}$); end for end;

Figure 3: Algorithm ComputeOptimalSolution.

Constraint satisfaction optimization problems naturally arise in various
application contexts. As an example they have recently been used in the
context of combinatorial auctions [13], in order to model and solve the
_winner determination problem_ of determining the allocation of the items
among the bidders that maximizes the sum of the accepted bid prices. In
particular, in [13], it has been observed that CSOPs and, in particular, the
winner determination problem, can be solved in polynomial time on some classes
of acyclic instances via a dynamic programming algorithm founded on the ideas
of [34]. This algorithm, named ComputeOptimalSolution, is reported in Figure 3
and will be briefly illustrated in the following.

The algorithm receives in input the instance $\langle\mathcal{I},{w}\rangle$
and a join tree $T=(N,E)$ for ${\cal H}(\mathcal{I})$. Recall that each vertex
$v\in N$ corresponds to a hyperedge of ${\cal H}(\mathcal{I})$ and, in its
turn, to a constraint in $\mathcal{C}$; hence, we shall simply denote by
$(S_{v},r_{v})$ the constraint in $\mathcal{C}$ univocally associated with
vertex $v$.

Based on $\langle\mathcal{I},{w}\rangle$ and $T$, ComputeOptimalSolution
computes an optimal solution (or checks that there is no solution) by looking
for the “conformance” of the tuples in each relation $r_{v}$ with the tuples
in $r_{c}$, for each child $c$ of $v$ in $T$, where ${t}_{v}\in r_{v}$ is said
to _conform_ with ${t}_{c}\in r_{c}$, denoted by ${t}_{v}\approx\ {t}_{c}$, if
for each $X\in S_{v}\cap S_{c}$, $X/u\in{t}_{v}\Leftrightarrow X/u\in{t}_{c}$.
In more detail, ComputeOptimalSolution solves $\langle\mathcal{I},{w}\rangle$
by traversing $T$ in two phases. First, vertices of $T$ are processed from the
leaves to the root $r$, by means of the procedure $BottomUp$ that updates the
weight $\ell_{{{t}_{v}}}^{v}$ of the current vertex $v$. Intuitively,
$\ell_{{{t}_{v}}}^{v}$ stores the cost of the best partial solution for
$\mathcal{I}$ computed by using only the variables occurring in the subtree
rooted at $v$. Indeed, if $v$ is a leaf, then
$\ell_{{{t}_{v}}}^{v}=w({t}_{v})$. Otherwise, for each child $c$ of $v$ in
$T$, $\ell_{{{t}_{v}}}^{v}$ is updated by adding the minimum value
$\ell_{{t}_{c}}^{c}-w({t}_{c}\cap{t}_{v})$ over all tuples ${t}_{c}$
conforming with ${t}_{v}$. The tuple $\bar{t}_{c}$ for which this minimum is
achieved is stored in the variable ${t}_{{t}_{v},c}$ (resolving ties
arbitrarily). Note that if this process cannot be completed, because there is
no tuple in $r_{v}$ conforming with some tuple in each relation associated
with the children of $v$, then we may conclude that $\mathcal{I}$ is not does
not admit any solution. Otherwise, after the root $r\in N$ is reached, this
part ends, and the top-down phase may start.

In this second phase, the tree $T$ is processed starting from the root.
Firstly, the assignment ${t}^{*}$ is defined as the tuple in $r_{r}$ with the
minimum cost over all the tuples in $r_{r}$ (again, resolving ties
arbitrarily). Then, procedure $TopDown$ extends ${t}^{*}$ with a tuple for
each vertex of $T$: at each vertex $v$ and for each child $c$ of $v$,
${t}^{*}$ is extended with the tuple ${t}_{{t}_{v},c}$ resulting from the
bottom-up phase.

Being based on a standard dynamic programming scheme, correctness of
ComputeOptimalSolution can be shown by structural induction on the subtrees of
$T$ [13]. Moreover, by analyzing its running time, one may note that dealing
with cost functions does not (asymptotically) provide any overhead w.r.t.
Yannakakis’s algorithm [34] for plain CSPs. Following [13], the following can
be shown for the more general case of CSOP instances having bounded
generalized hypertree-width hypergraphs.111In all complexity results, we
assume the weighting function ${w}$ be explicitly listed in the input
(otherwise, just add the cost of computing through ${w}$ all cost values for
the variable assignments of the given input instance).

###### Theorem 4.1

Let $\langle\mathcal{I},{w}\rangle$ be a CSOP instance and $H\\!D$ a
(generalized) hypertree decomposition of ${\cal H}(\mathcal{I})$. Moreover,
let $k$ be the width of $H\\!D$ and $m$ be the number of vertices in its
decomposition tree. Then, a solution to $\langle\mathcal{I},{w}\rangle$ can be
computed (or it is discovered that no solution exists) in time $O((m-1)\times
r_{max}^{k}\times\log r_{max}^{k})$, where $r_{max}$ is the size of the
largest constraint relation in $\mathcal{I}$.

###  4.2 Weighted CSPs: Costs over Tuples

Let us now turn to study a slight variation of the above scenario, where costs
are associated with each tuple of the constraint relations, rather than with
substitutions for individual variables. In fact, this is the setting of
weighted CSPs, a well-known specialization of the more general _valued_ CSP
framework [30].

Formally, a weighted CSP (WCSP) instance consists of a tuple
$\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$, where
$\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$ with
$\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{q}\\}$ is a CSP instance, and where, for
each tuple $t_{v}\in r_{v}$, ${w}_{v}(t_{v})\in\mathbb{Q}$ denotes the cost
associated with $t_{v}$. For a solution $\theta=t_{1}\cup...\cup t_{q}$ to
$\mathcal{I}$, we define ${w}(\theta)=\sum_{v=1}^{q}{w}_{v}(t_{v})$ as its
associated cost. Then, a solution to
$\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$ is a solution $\theta$ to
$\mathcal{I}$ such that ${w}(\theta)\leq{w}(\theta^{\prime})$, for each
solution $\theta^{\prime}$ to $\mathcal{I}$.

A few tractability results for WCSPs (actually, for valued CSPs) are known in
the literature when structural restrictions are considered over binary
encodings of the constraint hypergraphs. Indeed, it has been observed that
WCSPs are tractable when restricted on classes of instances whose associated
primal graphs are acyclic or nearly-acyclic (see, e.g., [33, 10, 26]).
However, the primal graph obscures much of the structure of the underlying
hypergraph since, for instance, each hyperedge is turned into a clique
there—see the discussion in Section 3.

Therefore, whenever constraints have large arities, tractability results for
primal graphs are useless, and it becomes then natural to ask whether
polynomial-time solvability still holds when moving from (nearly-)acyclic
primal graphs to acyclic hypergraphs, possibly associated with very intricate
primal graphs. Next, we shall positively answer this question, by simply
recasting weighted CSPs as constraint optimization problems, and by
subsequently solving them via the algorithm ComputeOptimalSolution. To this
end, given a WCSP instance $\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$, we
define its associated CSOP instance, denoted by
${\mbox{CSOP}}(\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle)$, as the pair
$\langle\mathcal{I}^{\prime},w^{\prime}\rangle$ with
$\mathcal{I}^{\prime}=\langle{\it
Var}^{\prime},U^{\prime},\mathcal{C}^{\prime}\rangle$ such that:

  * $\bullet$

${\it Var}^{\prime}={{\it Var}\cup\\{D_{1},...,D_{q}\\}}$, where each $D_{v}$
is a fresh auxiliary variable in $\mathcal{I}^{\prime}$;

  * $\bullet$

$U^{\prime}=U\cup\bigcup_{v=1}^{q}\bigcup_{t_{v}\in r_{v}}\\{u_{t_{v}}\\}$,
i.e., for each constraint $(S_{v},r_{v})\in\mathcal{C}$, $U^{\prime}$ contains
a fresh value for each tuple in $r_{v}$—intuitively, mapping the variable
$D_{v}$ to $u_{t_{v}}$ encodes that the tuple $t_{v}$ is going to contribute
to a solution for $\mathcal{I}$;

  * $\bullet$

$\mathcal{C}^{\prime}=\\{(S_{v}\cup\\{D_{v}\\},r_{v}^{\prime})\mid(S_{v},r_{v})\in\mathcal{C}\\}$,
where $r_{v}^{\prime}=\\{t_{v}\cup\\{D_{v}/u_{t_{v}}\\}\mid t_{v}\in
r_{v}\\}$;

  * $\bullet$

$w^{\prime}(X/u)=w_{v}(t_{v})$ if $X=D_{v}$ and $u=u_{t_{v}}$, for some tuple
$t_{v}\in r_{v}$; otherwise, $w^{\prime}(X/u)=0$. That is, the whole cost of
each tuple is determined by the mapping of its associated fresh variable
$D_{v}$.

It is immediate to check that the above transformation is feasible in linear
time. In addition, the transformation enjoys two relevant preservation
properties: Firstly, it preserves the structural properties of the WCSP
instance in that ${\cal H}(\mathcal{I}^{\prime})$ is acyclic if and only if
${\cal H}(P)$ is acyclic; and secondly, it preserves its solutions, in that
$\theta^{\prime}=t_{1}^{\prime}\cup...\cup t_{q}^{\prime}$ is a solution to
$\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$ if and only if
$\theta=t_{1}\cup...\cup t_{q}$ is a solution to
$\langle\mathcal{I}^{\prime},w^{\prime}\rangle$, where
$t_{v}^{\prime}=t_{v}\cup\\{D_{v}/u_{t_{v}}\\}$ for each $1\leq v\leq q$. By
exploiting these observations and Theorem 4.1, the following can be
established.

###### Theorem 4.2

Let $\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$ be a WCSP instance and
$H\\!D$ a (generalized) hypertree decomposition of ${\cal H}(\mathcal{I})$.
Moreover, let $k$ be the width of $H\\!D$ and $m$ be the number of vertices in
its decomposition tree. Then, a solution to
$\langle\mathcal{I},{w}_{1},...,{w}_{q}\rangle$ can be computed (or we may
state that there is no solution) in time $O((m-1)\times r_{max}^{k}\times\log
r_{max}^{k})$, where $r_{max}$ is the size of the largest constraint relation
in $\mathcal{I}$.

##  5 Minimizing the Number of Violated Constraints

In this section, we shall complete our picture by considering those scenarios
where problems might possibly be overconstrained and where, hence, the focus
is on finding assignment minimizing the total number of violated constraints.
These kinds of problems are usually referred to in the literature as Max-CSPs
[12], which similarly as WCSPs are specializations of valued CSPs.

Formally, let $\theta:{\it Var}\mapsto U$ be an assignment for a CSP instance
$\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$. We say that the violation
degree of $\theta$, denoted by $\delta(\theta)$, is the number of relations
$r_{v}$ such that there is no tuple $t_{v}\in r_{v}$ with
$t_{v}\subseteq\theta$. An assignment $\theta:{\it Var}\mapsto U$ is a
solution to the Max-CSP instance (associated with $\mathcal{I}$) if
$\delta(\theta)\leq\delta(\theta^{\prime})$, for each assignment
$\theta^{\prime}:{\it Var}\mapsto U$. Note that Max-CSPs instances, by
definition, do always have a solution.

###  5.1 Acyclic Instances Remain Intractable

After the tractability results established in Section 4.2 for WCSPs, one may
expect good news for Max-CSPs, too. Surprisingly, this is not the case.

###### Theorem 5.1

Solving Max-CSPs is $\rm NP$-hard, even when restricted over classes of
instances with acyclic constraint hypergraphs.

###### Proof

Consider any class $\mathcal{T}$ of CSPs instances having an NP-hard
satisfiability problem. Then, let $\mathcal{T}^{\prime}$ be a new class of
Max-CSP instances such that, for each $\mathcal{I}=\langle{\it
Var},U,\mathcal{C}\rangle\in\mathcal{T}$, $\mathcal{T}^{\prime}$ contains an
instance $\mathcal{I}^{\prime}=\langle{\it Var},U,\mathcal{C}^{\prime}\rangle$
with $\mathcal{C}^{\prime}=\mathcal{C}\cup\\{({\it Var},\emptyset)\\}$. That
is, any instance $\mathcal{I}^{\prime}\in\mathcal{T}^{\prime}$ has a
constraint over all variables with an empty constraint relation, and thus it
is not satisfiable. Moreover, because of the big hyperedge associated with
such a constraint, its hypergraph ${\cal H}(\mathcal{I}^{\prime})$ is
trivially acyclic. Also, by construction, there is an assignment for
$\mathcal{I}^{\prime}$ violating only one constraint if and only if
$\mathcal{I}$ is satisfiable. It follows that finding an assignment minimizing
the total number of violated constraints is NP-hard on the class of acyclic
instances $\mathcal{T}^{\prime}$. $\Box$

###  5.2 Incidence graphs and Tractable Cases

Given that hypergraph acyclicity and hence its generalizations are not
sufficient for guaranteeing the tractability of Max-CSPs, it makes sense to
explore acyclicity properties related to suitable graph representations. In
fact, as observed in Section 4.2, it is well-known that valued CSPs (and,
hence, Max-CSPs) are tractable over acyclic primal graphs (e.g., [33, 10,
26]). More precisely, tractability has been observed in the literature to hold
over primal graphs having bounded _treewidth_ (see Section 3). Our main result
in this section is precisely to show that tractability still holds in case the
_incidence graph_ of ${\cal H}(\mathcal{I})$ has bounded treewidth, which is a
more general condition than the bounded treewidth of primal graphs and which
can be used to establish better complexity bounds and to enlarge the class of
tractable instances [22]. The fact that the standard CSP is tractable for
instances whose incidence graphs have bounded treewidth was already shown in
[6]. We here extend this tractability result to Max-CSPs.

Recall that the incidence encoding of a hypergraph ${\cal H}$, denoted by
${\it inc}({\cal H})=(N,E)$, is the bipartite graph where
$N={\mathcal{E}}({\cal H})\cup{\mathcal{N}}({\cal H})$ and $E=\\{\
\\{h,a\\}\mid h\in{\mathcal{E}}({\cal H})\mbox{ and }a\in h)\\}$, i.e. it
contains an edge between $h$ and $a$ if and only if the variable $a$ occurs in
the hyperedge $h$. As an example, Figure 2 reports on the rightmost part the
incidence graph ${\it inc}({\cal H}_{1})$, where nodes associated with
hyperedges in ${\mathcal{E}}({\cal H}_{1})$ are depicted as black circles.
Note that the treewidth of ${\it inc}({\cal H}_{1})$ is 2, which is much
smaller than the treewidth of ${\it G}({\cal H}_{1})$. This does not happen by
chance since, for each hypergraph ${\cal H}$, it holds that $tw({\it
inc}({\cal H}))\leq tw({\it G}({\cal H}))$; in addition, there are also
classes of hypergraphs with incidence encodings of bounded treewidth and
primal encodings of unbounded treewdith (see, e.g., [22]).

While enlarging the class of instances having bounded treewidth, the incidence
encoding still conveys all the information needed to solve Max-CSP instances.
Again, the solution algorithm consists of a transformation into a suitable
CSOP instance. Formally, let $\mathcal{I}=\langle{\it
Var},U,\mathcal{C}\rangle$ be a Max-CSP instance with
$\mathcal{C}=\\{(S_{1},r_{1}),...,(S_{q},r_{q})\\}$, and let $\langle
T,\chi\rangle$ be a $k$-width tree decomposition of ${\it inc}({\cal
H}(\mathcal{I}))$—recall that for each vertex $v\in T$, $\chi(v)$ is a set of
variables (i.e., nodes of ${\mathcal{N}}({\cal H}(\mathcal{I}))$) and
constraint scopes (i..e, edges in ${\mathcal{E}}({\cal H}(\mathcal{I}))$).
Then, the constraint satisfaction optimization problem instance
${\mbox{CSOP}}(\mathcal{I},\langle T,\chi\rangle)$ is the pair
$\langle\mathcal{I}^{\prime},w^{\prime}\rangle$, where
$\mathcal{I}^{\prime}=\langle{\it
Var}^{\prime},U^{\prime},\mathcal{C}^{\prime}\rangle$ and such that:

  * $\bullet$

${\it Var}^{\prime}={\it Var}\cup\\{S_{1},...,S_{q}\\}$, that is, also the
constraint scopes of $\mathcal{C}$ belong to the variables of the new problem;

  * $\bullet$

$U^{\prime}=U\cup\\{\mathit{unsat}\\}\cup\\{u_{t}\mid t\in r_{i},\mbox{ for
}1\leq i\leq q\\}$;

  * $\bullet$

$\mathcal{C}^{\prime}=\\{(\chi(v),r^{\prime}_{v})\mid v\in T\\}$ where the
constraint relation $r^{\prime}_{v}$ is defined as follows. Let
$\mu=|\chi(v)\cap{\it Var}|$, and let $U^{\mu}$ denote the set of all possible
tuples over the $\mu$ variables in $\chi(v)\cap{\it Var}$. Let also
$S_{i_{1}},...S_{i_{h}}$ be the scope-variables in $\chi(v)$. Then, for each
tuple $\theta\in U^{\mu}$, the relation $r^{\prime}_{v}$ contains all tuples
$\theta\cup\\{S_{i_{1}}/v_{i_{1}}\\}\cup\cdots\cup\\{S_{i_{h}}/v_{i_{h}}\\}$,
where $v_{i_{j}}\in U$ ($1\leq j\leq h$) is a value for the scope-variable
$S_{i_{j}}$ such that: $v_{i_{j}}=u_{t}$ if there is a tuple $t\in r_{i_{j}}$
conforming with $\theta$; and $v_{i_{j}}=\mathit{unsat}$, if no such a tuple
exists in $r_{i_{j}}$.

  * $\bullet$

$w^{\prime}(X/u)=0$ if $u\neq\mathit{unsat}$; otherwise $w^{\prime}(X/u)=1$,
that is, each constraint of $\mathcal{C}$ that is not satisfied increases the
cost of a solution by a unitary factor.

Note that this transformation is feasible in time exponential in the width of
$\langle T,\chi\rangle$ only. Moreover, solutions of $\mathcal{I}^{\prime}$
with minimum total cost precisely correspond to assignments over $\mathcal{I}$
minimizing the total number of violated constraints. In fact, the following
can be established.

###### Theorem 5.2

Let $\mathcal{I}=\langle{\it Var},U,\mathcal{C}\rangle$ be a Max-CSP instance
with $tw({\it inc}({\cal H}(\mathcal{I})))=k$. Then, a solution to
$\mathcal{I}$ can be computed in time $O(|{\it
Var}|\times|U|^{k+1}\times\log|U|^{k+1})$.

##  6 Conclusion and Discussion

In this paper, classes of tractable CSOP, WCSP, and Max-CSP instances are
singled out by overviewing and proposing solution approaches applicable to
instances whose hypergraphs have bounded (generalized) hypertree width, or
whose incidence graphs have bounded treewidth. The techniques described in
this paper are mainly based on Algorithm ComputeOptimalSolution, which has
been designed to optimize costs expressed as rational numbers and combined via
the summation operation. However, it is easily seen that it remains correct if
costs are specified over an arbitrary totally ordered monoid structure, where
some binary operation $\oplus$ (in place of standard summation) is used in
order to combine costs, provided it is commutative, associative, closed, and
that it verifies identity and monotonicity. It follows that all tractable
classes of CSOP, WCSP, and Max-CSP instances identified in this paper remain
tractable in such extended scenarios, which indeed emerge with valued CSPs
(see, e.g., [4]).

## References

  * [1] I. Adler, G. Gottlob, and M. Grohe.  Hypertree-Width and Related Hypergraph Invariants.  European Journal of Combinatorics, 28, pp. 2167–2181, 2007.
  * [2] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis.  On the desirability of acyclic database schemes.  Journal of the ACM, 30(3), pp. 479–513, 1983.
  * [3] P.A. Bernstein and N. Goodman.  The power of natural semijoins.  SIAM Journal on Computing, 10(4), pp. 751–771, 1981.
  * [4] S.Bistarelli, U. Montanari, F. Rossi, T. Schiex, G. Verfaillie, and H. Fargier.  Semiring-Based CSPs and Valued CSPs: Frameworks, Properties,and Comparison.  _Constraints_ , 4(3), pp. 199–240, 1999.
  * [5] H.L. Bodlaender and F.V. Fomin.  A Linear-Time Algorithm for Finding Tree Decompositions of Small Treewidth.  SIAM Journal on Computing, 25(6), pp. 1305-1317, 1996.
  * [6] Ch. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited. Theoretical Computer Science Vol. 239, Issue 2, 28 May 2000, pp. 211-229, 2000. (Preliminary version in Proc. ICDT’07.) In Proc. International Conference on Database Theory 1997 (ICDT’97), Delphi, Greece, Jan. 1997, Springer LNCS, Vol. 1186, pp.56–70, 1997. Full version:
  * [7] D.A. Cohen, P.G. Jeavons, and M. Gyssens.  A unified theory of structural tractability for constraint satisfaction problems.  Journal of Computer and System Sciences, 74(5):721–743, 2008.
  * [8] C. Daskalakis and C.H. Papadimitriou.  Computing pure nash equilibria in graphical games via markov random fields.  In Proc. of ACM EC’06, pp. 91–99, 2006.
  * [9] R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3):514–550, 1983.
  * [10] S. de Givry, T. Schiex, and G. Verfaillie.  Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP.  In Proc. of AAAI’06, 2006.
  * [11] R. Dechter.  Constraint Processing.  Morgan Kaufmann, 2003.
  * [12] E.C. Freuder and R.J. Wallace.  Partial Constraint Satisfaction.  Artificial Intelligence, 58(1-3), pp. 21–70, 1992.
  * [13] G. Gottlob and G. Greco.  On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition.  In Proc. EC’07, pp. 152–161, 2007. [full version currently available as Technical Report, University of Calabria]
  * [14] G. Gottlob, G. Greco, and F. Scarcello.  Pure Nash Equilibria: Hard and Easy Games.  Journal of Artificial Intelligence Research, 24, pp. 357–406, 2005.
  * [15] G. Gottlob, N. Leone, and F. Scarcello.  A comparison of structural CSP decomposition methods.  Artificial Intelligence, 124(2), pp. 243–282, 2000.
  * [16] G. Gottlob, N. Leone, and F. Scarcello.  The complexity of acyclic conjunctive queries.  Journal of the ACM, 48(3), pp. 431–498, 2001.
  * [17] G. Gottlob, N. Leone, and F. Scarcello.  Advanced parallel algorithms for processing acyclic conjunctive queries, rules, and constraints.  In Proc. of SEKE’00, pp. 167–176, 2000.
  * [18] G. Gottlob, N. Leone, and F. Scarcello.  Hypertree decompositions and tractable queries.  J. of Computer and System Sciences, 64(3), pp. 579–627, 2002.
  * [19] G. Gottlob, N. Leone, and F. Scarcello.  Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width.  J. of Computer and System Sciences, 66(4), pp. 775–808, 2003.
  * [20] G. Gottlob, Z. Miklós, and T. Schwentick.  Generalized hypertree decompositions: NP-hardness and tractable variants.  In Proc. of PODS’07, pp. 13-22, 2007.
  * [21] G. Gottlob, R. Pichler, and F. Wei.  Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning.  In Proc. of AAAI’06.
  * [22] G. Greco and F. Scarcello.  Non-Binary Constraints and Optimal Dual-Graph Representations.  In Proc. of IJCAI’03, pp. 227-232, 2003.
  * [23] M. Grohe and D. Marx.  Constraint solving via fractional edge covers.  In Proc. of SODA’06, pp. 289–298, Miami, Florida, USA, 2006.
  * [24] K. Kask, R. Dechter, J. Larrosa, and A. Dechter.  Unifying tree decompositions for reasoning in graphical models.  Artificial Intelligence, 166(1-2), pp. 165–193, 2005.
  * [25] P. Meseguer, F. Rossi and T. Schiex.  Soft Constraints.  Handbook of Constraint Programming, Elsevier, 2006.
  * [26] S. Ndiaye, P. J gou, and C. Terrioux.  Extending to Soft and Preference Constraints a Framework for Solving Efficiently Structured Problems.  In Proc. of ICTAI’08, pp. 299–306, 2008.
  * [27] O. Reingold.  Undirected ST-connectivity in log-space,  Journal of the ACM, 55(4), 2008.
  * [28] N. Robertson and P.D. Seymour.  Graph minors III: Planar tree-width.  Journal of Combinatorial Theory, Series B, 36, pp. 49- 64, 1984.
  * [29] F. Scarcello, G. Gottlob, and G. Greco.  Uniform Constraint Satisfaction Problems and Database Theory.  In Complexity of Constraints, LNCS 5250, pp. 156- 195, Springer-Verlag, 2008.
  * [30] T. Schiex, H. Fargier, and G. Verfaillie.  Valued Constraint Satisfaction Problems: Hard and Easy Problems.  In Proc. of IJCAI’95, pp. 631–639, 1995.
  * [31] R.E. Tarjan, and M. Yannakakis.  Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs.  SIAM Journal on Computing, 13(3):566-579, 1984.
  * [32] E. Tsang.  Foundations of Constraint Satisfaction.  Academic Press, 1993.
  * [33] C. Terrioux and P. J’egou.  Bounded Backtracking for the Valued Constraint Satisfaction Problems.  In Proc. of CP’03, pp. 709–723, 2003.
  * [34] M. Yannakakis.  Algorithms for acyclic database schemes.  In Proc. of VLDB’81, pp. 82–94, 1981.