theoremTheorem lemma[theorem]Lemma corollary[theorem]Corollary [500]Theory of
computation Constraint and logic programming [500]Theory of computation
Complexity theory and logic Technische Universität Ilmenau, Ilmenau,
<EMAIL_ADDRESS>by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - project
number 414325841. Univ. Artois, CNRS, Centre de Recherche en Informatique de
Lens<EMAIL_ADDRESS>work has been partially supported by the ANR
project EQUUS ANR-19-CE48-0019. Technische Universität Ilmenau, Ilmenau,
<EMAIL_ADDRESS>by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) - project number
414325841.

# A characterization of efficiently compilable constraint languages

Christoph Berkholz  Stefan Mengel  Hermann Wilhelm

###### Abstract

A central task in _knowledge compilation_ is to compile a CNF-SAT instance
into a succinct representation format that allows efficient operations such as
testing satisfiability, counting, or enumerating all solutions. Useful
representation formats studied in this area range from ordered binary decision
diagrams (OBDDs) to circuits in decomposable negation normal form (DNNFs).

While it is known that there exist CNF formulas that require exponential size
representations, the situation is less well studied for other types of
constraints than Boolean disjunctive clauses. The _constraint satisfaction
problem_ (CSP) is a powerful framework that generalizes CNF-SAT by allowing
arbitrary sets of constraints over any finite domain. The main goal of our
work is to understand for which type of constraints (also called the
_constraint language_) it is possible to efficiently compute representations
of polynomial size. We answer this question completely and prove two tight
characterizations of efficiently compilable constraint languages, depending on
whether target format is structured.

We first identify the combinatorial property of “strong blockwise
decomposability” and show that if a constraint language has this property, we
can compute DNNF representations of linear size. For all other constraint
languages we construct families of CSP-instances that provably require DNNFs
of exponential size. For a subclass of “strong _uniformly_ blockwise
decomposable” constraint languages we obtain a similar dichotomy for
_structured_ DNNFs. In fact, strong (uniform) blockwise decomposability even
allows efficient compilation into multi-valued analogs of OBDDs and FBDDs,
respectively. Thus, we get complete characterizations for all knowledge
compilation classes between O(B)DDs and DNNFs.

###### keywords:

constraint satisfaction, knowledge compilation, dichotomy, DNNF

##  1 Introduction

One of the main aims of _knowledge compilation_ is to encode solution sets of
computational problems into a succinct but usable form [DarwicheM02]. Typical
target formats for this compilation process are different forms of decision
diagrams [Wegener00] or restricted classes of Boolean circuits. One of the
most general representation formats are circuits in _decomposable negation
normal form_ (DNNF), which have been introduced in [Darwiche01] as a
compilation target for Boolean functions. Related notions, which also rely on
the central decomposability property, have been independently considered in
databases [OlteanuZ15, Olteanu16] and circuit complexity [RazSY08, AlonKV20].
Besides these, DNNF circuits and related compilation classes have also been
proven useful in areas like probabilistic inference [BroeckS17], constraint
satisfaction [KoricheLMT15, BerkholzV23, AmilhastreFNP14, MateescuD06], MSO
evaluation [AmarilliBJM17], QBF solving [CapelliM19], to name a few. The DNNF
representation format has become a popular data structure because it has a
particularly good balance between generality and usefulness [DarwicheM02].
There has also been a large amount of practical work on compiling solution
sets into DNNF or its fragments, see e.g. [LagniezM17, Darwiche04, MuiseMBH12,
ChoiD13, OztokD15, KoricheLMT15]. In all these works, it assumed that the
solutions to be compiled are given as a system of constraints, often as a set
of disjunctive Boolean clauses, i. e., in conjunctive normal form (CNF).

In this setting, however, strong lower bounds are known: it was shown that
there are CNF-formulas whose representation as DNNF requires exponential size
[BovaCMS14, BovaCMS16, Capelli17, AmarilliCMS20]. The constraints out of which
the hard instances in [BovaCMS14, AmarilliCMS20, Capelli17] are constructed
are very easy—the are only monotone clauses of two variables. Faced with these
negative results, it is natural to ask if there are any classes of constraints
that guarantee efficient compilability into DNNF.

We answer this question completely and prove a tight characterization for
every constraint language $\Gamma$. We first examine the combinatorial
property of _strong blockwise decomposability_ and show that if a constraint
language $\Gamma$ has this property, any system of constraints over $\Gamma$
can be compiled into a DNNF representation of linear size within polynomial
time. Otherwise, there are systems of constraints that require exponential
size DNNF representations. In the tractable case, one can even compile to the
restricted fragment of _free decision diagrams_ (FDD) that are in general
known to be exponentially less succinct than DNNF [Wegener00, DarwicheM02].

We also consider the important special case of so-called structured DNNF
[PipatsrisawatD08] which are a generalization of the well-known ordered binary
decision diagrams [Bryant86]. We show that there is a restriction of strong
blockwise decomposability that determines if systems of constraints over a set
$\Gamma$ can be compiled into structured DNNF in polynomial time. In the
tractable case, we can in fact again compile into a restricted fragment, this
time ordered decision diagrams (ODD).

Let us stress that all our lower bounds are unconditional and do not depend on
any unproven complexity assumptions.

#### Further related work.

Our work is part of a long line of work in constraint satisfaction, where the
goal is to precisely characterize those constraint languages that are
“tractable”. Starting with the groundbreaking work of Schaefer [Schaefer78]
which showed a dichotomy for deciding consistency of systems of _Boolean_
constraints, there has been much work culminating in the dichotomy for general
constraint languages [Bulatov17, Zhuk17]. Beyond decision, there are
dichotomies for counting [CreignouH96, Bulatov08, DyerR13], enumeration
[CreignouOS11], optimization [Creignou95, KhannaSTW00, CreignouKS2001] and
many other problems. Note that the hardness part (showing that certain
constraint languages do not admit efficient algorithms) always relies on some
complexity theoretic assumption.

The complexity of constraint satisfaction has also been studied “from the
other side”, where the constraint language is unrestricted and the structure
of the _constraint network_ (i. e. how the constraints are arranged) has been
analyses. In this setting, characterizations of (bounded arity) constraint
networks have been obtained for the deciding the existence of solutions
[Grohe2007] and counting solutions [DalmauJ04] (again, under some complexity
theoretic assumption). Recently, an unconditional characterization of (bounded
arity) constraint networks that allow efficient compilation into DNNFs has
also been obtained [BerkholzV23].

Out of these works, our results are most closely related to the counting
dichotomy of [DyerR13]. The tractable classes we obtain in our dichotomies are
also tractable for counting, and in fact we use the known counting algorithm
in our compilation algorithms as a subroutine. Also, the tractability
criterion has a similar flavor, but wherever in [DyerR13] the count of
elements in certain relations is important, for our setting one actually has
to understand their structure and how exactly they decompose. That said, while
the tractability criterion is related to the one in [DyerR13], the techniques
to show our results are very different. In particular, where [DyerR13] use
reductions from #P-complete problems to show hardness, we make an explicit
construction and then use communication complexity to get strong,
unconditional lower bounds. Also, our two algorithms for construction ODDs and
FDDs are quite different to the counting algorithm.

#### Outline of the paper.

After some preliminaries in Section 2, we introduce the decomposability
notions that we need to formulate our results in Section 3. We also give the
formal formulation of our main results there. In Section 4, we show some of
the properties of the constraints we defined in the section before. These
properties will be useful throughout the rest of the paper. In Section 5, we
present the algorithms for the positive cases of our dichotomies, then, in
Section 6, we show the corresponding lower bounds. We specialize our results
to the case of Boolean relations in Section 7, showing that the tractable
cases are essentially only equalities and disequalities. Finally, we conclude
in Section 8.

##  2 Preliminaries

#### Constraints.

Throughout the paper we let $D$ be a finite _domain_ and $X$ a finite set of
_variables_ that can take values over $D$. We typically denote variables by
$u,v,w,x,y,z$ and domain elements by $a,b,c,d$. A $k$-tuple
$(x_{1},\ldots,x_{k})\in X^{k}$ of variables is also denoted by
$\vec{x}=x_{1}x_{2}\cdots x_{k}$ and we let
$\tilde{x}:=\\{x_{1},\ldots,x_{k}\\}$ be the set of variables occurring in
$\vec{x}$. We use the same notation for tuples of domain elements. A _$k$ -ary
relation_ $R$ (over $D$) is a set $R\subseteq D^{k}$. A _$k$ -ary constraint_
(over $X$ and $D$), denoted by $R(\vec{x})$, consists of a $k$-tuple of (not
necessarily distinct) variables $\vec{x}\in X^{k}$ and a $k$-ary relation
$R\subseteq D^{k}$. For a constraint $R(\vec{x})$ we call $\tilde{x}$ the
_scope_ of the constraint and $R$ the _constraint relation_. The _solution
set_ of a constraint $R(x_{1},\ldots,x_{k})$ is defined by
$\operatorname{sol}(R(x_{1},\ldots,x_{k})):=\\{\beta\mid\beta\colon\\{x_{1},\ldots,x_{k}\\}\to
D;\,(\beta(x_{1}),\ldots,\beta(x_{k}))\in R\\}$. Since the order of the
columns in a constraint relation is not of great importance for us, we often
identify constraints with their solution set and treat sets $\mathcal{S}$ of
mappings from $Y\subseteq X$ to $D$ as a constraint with scope $Y$ and
solution set $\mathcal{S}$. Moreover, for readability we will often write, e.
g., “a constraint $R(x,y,\vec{w})$, such that $x$ and $y$ …” when we do not
strictly require $x$ and $y$ to be at the first and second position and
actually refer to any constraint having $x$ and $y$ in its scope.

#### CSP-instance and constraint language.

A _constraint satisfaction instance_ $I=(X,D,C)$ consists of a finite set of
variables $X$, a finite domain $D$, and a finite set $C$ of constraints. The
solution set $\operatorname{sol}(I):=\\{\alpha\mid\alpha\colon X\to
D;\;\alpha|_{\tilde{x}}\in\operatorname{sol}(R(\vec{x}))\text{ for all
}R(\vec{x})\in C\\}$ of an instance $I$ is the set of mappings from $X$ to $D$
that satisfies all constraints. A _constraint language_ $\Gamma$ is a finite
set of relations (over some finite domain $D$). A constraint satisfaction
instance $I$ is a $\operatorname{CSP}(\Gamma)$-instance if every constraint
relation $R$ occurring in $I$ is contained in the constraint language
$\Gamma$.

#### Conjunction and projection.

A _conjunction_ $R(\vec{u})=S(\vec{v})\land T(\vec{w})$ of two constraints
$S(\vec{v})$ and $T(\vec{w})$ defines a constraint $R(\vec{u})$ over
$\vec{u}=u_{1}\cdots u_{\ell}$ with scope $\tilde{u}=\tilde{v}\cup\tilde{w}$
and constraint relation
$R:=\\{(\beta(u_{1}),\ldots,\beta(u_{\ell}))\mid\beta\colon\tilde{u}\to
D;\;\beta|_{\tilde{v}}\in\operatorname{sol}(S(\vec{v}))\text{ and
}\beta|_{\tilde{w}}\in\operatorname{sol}(T(\vec{w}))\\}$.111Again, we may just
write “$S(\vec{v})\land T(\vec{w})$” instead of “$R(\vec{u})=S(\vec{v})\land
T(\vec{w})$” if the order or multiple occurrences of variables in $\vec{u}$
does not matter (the solution set $\operatorname{sol}(R(\vec{u}))$ is always
the same). If $\tilde{v}\cap\tilde{w}=\emptyset$, then a conjunction is called
a _(Cartesian) product_ and written $R(\vec{u})=S(\vec{v})\times T(\vec{w})$.
For a constraint $R(\vec{x})$ and a set $Y\subseteq\tilde{x}$ we let the
_projection_ $\pi_{Y}R(\vec{x})$ be the constraint $S(\vec{y})$ with scope
$\tilde{y}=Y$ obtained by projecting the constraint relation to corresponding
coordinates, i. e., for $\vec{x}=x_{1}\cdots x_{k}$ let $1\leq
i_{1}<\cdots<i_{\ell}\leq k$ s. t. $\\{i_{1},\ldots,i_{\ell}\\}=\\{i\mid
x_{i}\in Y\\}$, $\vec{y}:=x_{i_{1}}\cdots x_{i_{\ell}}$, and
$S:=\\{(a_{i_{1}},\ldots,a_{i_{\ell}})\mid(a_{1},\ldots,a_{k})\in R\\}$.

#### Formulas and pp-definability.

A _$\Gamma$ -formula_ $F(\vec{x})=\bigwedge_{i}S_{i}(\vec{x}_{i})$ is a
conjunction over several constraints whose constraint relations are in
$\Gamma$. To avoid notational clutter, we use “$F(\vec{x})$” for both, the
conjunction as syntactic expression _and_ the constraint defined by this
formula. Note that any CSP($\Gamma$)-instance $I=(X,D,C)$ corresponds to a
$\Gamma$-formula $F(\vec{x})=\bigwedge_{R_{i}(\vec{x}_{i})\in
C}R_{i}(\vec{x}_{i})$ with $\tilde{x}=X$ and
$\operatorname{sol}(F(\vec{x}))=\operatorname{sol}(I)$. Thus, we can treat
CSP($\Gamma$)-instances as $\Gamma$-formulas and vice versa. A _primitive
positive (pp)_ formula over $\Gamma$ is an expression
$F(\vec{y})=\pi_{\tilde{y}}(\bigwedge_{i}S_{i}(\vec{x}_{i})\land\bigwedge_{(j,k)}x_{j}=x_{k})$
consisting of a projection applied to a $\Gamma\cup\big{\\{}\\{(a,a)\mid a\in
D\\}\big{\\}}$-formula, which uses constraint relations from $\Gamma$ and the
equality constraint. Note that conjunctions of pp-formulas can be written as
pp-formula by putting one projection at the front and renaming variables. A
constraint is _pp-definable_ over $\Gamma$, if it can be defined by a pp-
formula over $\Gamma$. Moreover, a relation $R\subseteq D^{k}$ is _pp-
definable_ over $\Gamma$ if it is the constraint relation of a pp-definable
constraint $R(x_{1},\ldots,x_{k})$ for pairwise distinct $x_{1},\ldots,x_{k}$.
The co-clone $\langle\Gamma\rangle$ of $\Gamma$ is the set of all pp-definable
relations over $\Gamma$.

#### Selection.

It is often helpful to use additional unary relations $S\subseteq D$ and to
write $U_{S}(x)$ for the constraint $S(x)$ with scope $\\{x\\}$ and constraint
relation $S$. We use $U_{a}(x)$ as an abbreviation for $U_{\\{a\\}}(x)$. For a
constraint $R(\vec{u})$, a variable $x\in\tilde{u}$, and a domain element
$a\in D$ we define the _selection_ $R(\vec{u})|_{x=a}$ be the constraint
obtained by forcing $x$ to take value $a$, that is,
$R(\vec{u})|_{x=a}:=R(\vec{u})\land U_{a}(x)$. Similarly, for a set
$S\subseteq D$ we write $R(\vec{u})|_{x\in S}:=R(\vec{u})\land U_{S}(x)$.

#### DNNF.

We will be interested in circuits representing assignments of variables to a
finite set of values. To this end, we introduce a multi-valued variant of
DNNF; we remark that usually DNNF are only defined over the Boolean domain
$\\{0,1\\}$ [Darwiche01], but the extension we make here is straightforward
and restricted variants have been studied e.g. in [KoricheLMT15,
AmilhastreFNP14, MateescuDM08, FargierM06] under different names.

Let $X$ be a set of variables and $D$ be a finite set of values. A circuits
over the operations $\times$ and $\cup$ is a directed acyclic graph with a
single sink, called output gate, and whose inner nodes, called gates, are
labeled with $\times$ or $\cup$. The source-nodes, called inputs of the
circuit, are labeled by expressions of the form $x\mapsto a$ where $x\in X$
and $a\in D$. We say that $\times$-gate $v$ is _decomposable_ if there are no
two inputs labeled with $x\mapsto a$ and $x\mapsto b$ (with possibly $a=b$)
that have a path to $v$ going through different children of $v$. A DNNF is a
circuit in which all $\times$-gates are decomposable. Note that in a DNNF, for
every $\times$-gate $v$, every variable $x\in X$ can only appear below one
child of $v$.

For every DNNF $O$ we define the set $S(O)$ of assignments _captured_ by $O$
inductively:

  * •

The set captured by an input $v$ with label $x\mapsto d$ is the single element
set $S(v)=\\{x\mapsto d\\}$.

  * •

For a $\cup$-gate with children $v_{1},v_{2}$, we set $S(v):=S(v_{1})\cup
S(v_{2})$.

  * •

For a $\times$-gate with children $v_{1},v_{2}$, we set $S(v):=S(v_{1})\times
S(v_{2})$ where for two assignments $a:X_{1}\rightarrow D$ and
$b:X_{2}\rightarrow D$, we interpret $(a,b)$ as the joined assignment
$c:X_{1}\cup X_{2}\rightarrow D$ with $c(x):=\begin{cases}a(x),&\text{ if
}x\in X_{1}\\\ b(x),&\text{ if }x\in X_{2}\end{cases}.$

We define $S(O):=S(v_{o})$ where $v_{o}$ is the output gate of $O$. Note that
$S(O)$ is well-defined in the case of $\times$, since $X_{1}$ and $X_{2}$ are
disjoint because of decomposability. Finally, we say that $O$ accepts an
assignment $\alpha$ to $X$ if there is an assignment $\beta\in S(O)$ such that
$\alpha$ is an extension of $\beta$ to all variables in $X$. We say that $O$
represents a constraint $C(\vec{x})$ if $O$ accepts exactly the assignments in
$\operatorname{sol}(C(\vec{x}))$.

A v-tree of a variable set $X$ is a rooted binary tree whose leaves are in
bijection to $X$. For a v-tree $T$ of $X$ and a node $t$ of $T$ we define
$\mathrm{var}(t)$ to be the variables in $X$ that appear as labels in the
subtree of $T$ rooted in $t$. We say that a DNNF $O$ over $X$ is _structured
by $T$_ if for every sub-representation $O^{\prime}$ of $O$ there is a node
$t$ in $T$ such that $O^{\prime}$ is exactly over the variables
$\mathrm{var}(t)$ [PipatsrisawatD08]. We say that $O$ is _structured_ if there
is a v-tree $T$ of $X$ such that $O$ is structured by $T$.

In the constructions in this appendix, it will be convenient to have a
slightly generalized variant of DNNF: besides the inputs of the form
$\\{x\mapsto a\\}$, we also allow inputs $\emptyset$ and $\\{\varepsilon\\}$.
To extend the semantics of DNNF to these new inputs, we define
$S(\emptyset)=\emptyset$ and $S(\varepsilon):=\\{\varepsilon\\}$ where
$\varepsilon$ is the unique assignment to $D$ with empty variable scope. We
observe that this slight extension does not increase the expressivity of the
model.

######  Lemma 2.1.

Every DNNF with inputs $\emptyset$ can be turned into a DNNF without such
inputs in polynomial time.

######  Proof 2.2.

We first show this for $\emptyset$-gates. So let $O$ be a DNNF and $v$ an
$\emptyset$-input in $O$. There are two cases: if the parent of $v$ is an
$\cup$-gate $u$, then we delete $v$ and substitute $u$ by its other child. By
definition of the semantics, this does not change the assignments captured in
any of the gates still in the DNNF after the operation. If $u$ is a
$\times$-gate, then by definition $S(u)=\emptyset$. But then we can simplify
the circuit by substituting $u$ by $v$ and iterating the construction.

We will use the following basic results on DNNF which correspond to projection
and selection on constraints.

Let $C(\vec{u})$ be a constraint for which there exists a DNNF of size $s$,
$x\in\tilde{u}$ and $A\subseteq D$. Then there exists a DNNF for the selection
$C(\vec{u})|_{x\in A}$ of size at most $s$.

######  Proof 2.3.

Let $O$ be the DNNF computing $C(\vec{u})$. We simply substitute all inputs in
$O$ that have the form $x\mapsto a$ for $a\notin A$ by $\emptyset$. A simple
induction shows that for every get $v$ of $O$ we then have that $S(v)$
contains exactly all assignments from from before that do not assign a value
from $D\setminus A$ to $x$. The claim directly follows with Lemma 2.1.

For the proof of Lemma 2, we will use the concept of _proof trees_ , which are
a classical notion from circuit complexity, sometimes under different names
like _parse trees_ or simply _certificates_ , see e.g. [Venkateswaran87,
MalodP08, BovaCMS16]. A proof tree $T$ of a DNNF $O$ is defined to be a
subcircuit of $O$ that

  * •

contains the output gate of $O$,

  * •

contains, for every $\times$-gate of $O$, both children of that gate,

  * •

contains, for every $\cup$-gate of $O$, exactly one child of that gate, and

  * •

contains no other gate.

Note that $O$ may in general have an exponential number of proof trees. Every
proof tree of $O$ is a DNNF that has as its underlying graph a tree. As a
DNNF, $T$ captures a set of assignments to the variables of $O$, and, from the
definition of proof trees, we directly get $S(T)\subseteq S(O)$. Moreover, if
we let $\mathcal{T}(O)$ denote all proof trees of $O$, then

$\displaystyle S(O):=\bigcup_{T\in\mathcal{T}(O)}S(T),$ (1)

so every assignment captured by $O$ gets captured by (at least) one of the
proof trees of $O$.

Let $C(\vec{u})$ be a constraint for which there exists a DNNF of size $s$ and
$\tilde{v}\in\tilde{u}$. Then there exists a DNNF for the projection
$\pi_{\tilde{v}}(C(\vec{u}))$ of size at most $s$.

######  Proof 2.4.

Assume w.l.o.g. that $\tilde{u}\setminus\tilde{v}$ contains only a single
variable $x$. If this is not the case, we can simply iterate the construction,
projecting away one variable at a time.

Let $O$ be the DNNF computing $C(\vec{u})$. We construct a new DNNF
$O^{\prime}$ over $\tilde{v}$ by substituting every input $x\mapsto a$ for
$a\in D$ by $\varepsilon$. We claim that $O^{\prime}$ computes
$\pi_{\vec{v}}(C(\vec{u}))$. Since up to the input labels $O$ and $O^{\prime}$
have the same $v$-trees, is suffices to show this for every proof tree. So let
$T$ be a proof tree in $O$ and $T^{\prime}$ the corresponding proof tree in
$O^{\prime}$. Let $a$ be an assignment captured by $T$. If $T$ does not
contain an input of the form $x\mapsto a$, then $T$ and $T^{\prime}$ are
equal, so there is nothing to show. If $T$ contains such an input, then it
contains exactly one of them due to decomposabilty. Let $\alpha$ be an
assignment captured by $T$, then $\alpha|_{\tilde{v}}$ is captured by
$T^{\prime}$, so $\pi_{\tilde{v}}(S(T))\subseteq S(T^{\prime})$. For the other
direction, fix $x\in S(T^{\prime})$. Then $\alpha$ does not assign a value to
$x$. But by assumption there is an input $x\mapsto a$ in $T$, so all
assignments in $S(T)$ assign $x$ to $a$. In particular, there is an assignment
$\beta\in S(T)$ that extends $\alpha$ to $x$. Thus $a\in\pi_{\tilde{v}}(T)$
and the claim follows.

#### Decision Diagrams.

A decision diagram $O$ over a variable set $X$ is a directed acyclic graph
with a single source and two sinks and in which all non-sinks have $|D|$
outgoing edges. The sinks are labeled with $0$ and $1$, respectively, while
all other nodes are labeled with variables from $x$. For every non-sink, the
$|D|$ outgoing edges are labeled in such a way that every value in $D$ appears
in exactly one label. Given an assignment $\alpha$ to $X$, the value computed
by $O$ is defined as follows: we start in the source and iteratively follow
the edge labeled by $\alpha(x)$ where $x$ is the label of the current node. We
continue this process until we end up in a leaf whose label then gives the
value of $O$ on $\alpha$. Clearly, this way $O$ computes a constraint over $X$
with relation $\\{\alpha\mid O\text{ computes }1\text{ on input }\alpha\\}$.

We are interested in decision diagrams in which on every source-sink-path
every variable appears at most once as a label. We call these diagrams _free
decision diagrams (FDD)_. An FDD for which there is an order $\pi$ such that
when a variable $x$ appears before $y$ on a path then $x$ also appears before
$y$ in $\pi$ is called _ordered decision diagrams_. We remark that FDD and ODD
are in the literature mostly studied for the domain $\\{0,1\\}$ in which case
they are called FBDD and OBDD, respectively, where the “B” stands for binary.
Note also that there is an easy linear time translation of FDD into DNNF and
ODD into structured DNNF, see e.g. [DarwicheM02]. In the other direction there
are no efficient translations, see again [DarwicheM02].

#### Rectangles.

Let $\vec{u}$ be a variable vector, $\tilde{u}=\tilde{x}\cup\tilde{y}$ and
$\tilde{x}\cap\tilde{y}=\emptyset$. Then we say that the constraint
$R(\vec{u})$ is a _(combinatorial) rectangle_ with respect to the partition
$(\tilde{x},\tilde{y})$ if and only if
$R(\vec{u})=\pi_{\tilde{x}}(R(\vec{u}))\times\pi_{\tilde{y}}(R(\vec{u}))$. Let
$Z\subseteq\tilde{u}$. Then we call the partition $(\tilde{x},\tilde{y})$ _$Z$
-balanced_ if $\frac{|Z|}{3}\leq|\tilde{x}\cap Z|\leq\frac{2|Z|}{3}$. A
constraint $R(\vec{u})$ is called a _$Z$ -balanced rectangle_ if it is a
rectangle with respect to a $Z$-balanced partition. A _$Z$ -balanced rectangle
cover_ $\mathcal{R}$ of a constraint $R(\vec{u})$ is defined to be a set of
$Z$-balanced rectangles such that
$\operatorname{sol}(R(\vec{u})):=\bigcup_{\mathfrak{r}\in\mathcal{R}}\operatorname{sol}(\mathfrak{r}(\vec{u}))$.
The size of $\mathcal{R}$ is the number of rectangles in it.

##  3 Blockwise decomposability

In this section we introduce our central notion of blockwise and uniformly
blockwise decomposable constraints and formulate our main theorems that lead
to a characterization of efficiently representable constraint languages.

The first simple insight is the following. Suppose two constraints
$S(\vec{v})$ and $T(\vec{w})$ with disjoint scopes are efficiently
representable, e. g., by a small ODD. Then their Cartesian product
$R(\vec{v},\vec{w})=S(\vec{v})\times T(\vec{w})$ also has a small ODD: given
an assignment $(\vec{a},\vec{b})$, we just need to check independently whether
$\vec{a}\in S$ and $\vec{b}\in T$, for example, by first using the ODD for
$S(\vec{v})$ and then using the ODD for $T(\vec{w})$. Thus, if a constraint
can be expressed as a Cartesian product of two constraints, we only have to
investigate whether the two parts are easy to represent. This brings us to our
first definition.

######  Definition 3.1.

Let $R(\vec{u})$ be a constraint and $(V_{1},\ldots,V_{\ell})$ be a partition
of its scope. We call $R(\vec{u})$ _decomposable w.r.t.
$(V_{1},\ldots,V_{\ell})$_ if
$R(\vec{u})=\pi_{V_{1}}(R(\vec{u}))\times\cdots\times\pi_{V_{\ell}}(R(\vec{u}))$.
A constraint $R(\vec{u})$ is _indecomposable_ if it is only decomposable
w.r.t. trivial partitions $(V_{1},\ldots,V_{\ell})$ where $V_{i}=\emptyset$ or
$V_{i}=\tilde{u}$ for $i\in[\ell]$.

Next, we want to relax this notion to constraints that are “almost”
decomposable. Suppose we have four relations $S_{1},S_{2}$ of arity $s$ and
$T_{1},T_{2}$ of arity $t$ and let $a,b$ be two distinct domain elements. Let

$R:=(\\{(a,a)\\}\times S_{1}\times T_{1})\cup(\\{(b,b)\\}\times S_{2}\times
T_{2}).$ (2)

The constraint $R(x,y,\vec{v},\vec{w})$ may now not be decomposable in any
non-trivial variable partition. However, after fixing values for $x$ and $y$
the remaining selection $R(x,y,\vec{v},\vec{w})|_{x=c,y=d}$ is decomposable in
$(\tilde{v},\tilde{w})$ for any pair $(c,d)\in D^{2}$. Thus, an ODD could
first read values for $x,y$ and then use ODDs for $S_{1}(\vec{v})$ and
$T_{1}(\vec{w})$ if $x=y=a$, ODDs for $S_{2}(\vec{v})$ and $T_{2}(\vec{w})$ if
$x=y=b$, or reject otherwise. This requires, of course, that $S_{1}(\vec{v})$
and $S_{2}(\vec{v})$, as well as $T_{1}(\vec{w})$ and $T_{2}(\vec{w})$, have
small ODDs over the _same_ variable order. For FDDs and DNNFs, however, we
would not need this requirement on the variable orders.

To reason about the remaining constraints after two variables have been fixed,
it is helpful to use the following matrix notation. Let $R(\vec{u})$ be a
constraint and $x,y\in\tilde{u}$ be two variables in its scope. The _selection
matrix_ $M^{R}_{x,y}$ is the $|D|\times|D|$ matrix where the rows and columns
are indexed by domain elements $a_{i},a_{j}\in D$ and the entries are the
constraints

$M^{R}_{x,y}[a_{i},a_{j}]:=\pi_{\tilde{u}\setminus\\{x,y\\}}(R(\vec{u})|_{x=a_{i},y=b_{j}}).$
(3)

######  Example 3.2.

Let $D=\left\\{a,b,c\right\\}$ and $R(x,y,z,v)$ a constraint with constraint
relation
$R=\left\\{\left(a,a,a,a\right),\left(b,b,a,b\right),\left(b,b,a,c\right),\left(b,b,c,c\right),\left(c,b,c,a\right)\right\\}.$
The selection matrix in $x$ and $y$ is depicted below, where the first line
and column are the indices from $D$ and the matrix entries contain the
constraint relations of the corresponding constraints
$M^{R}_{x,y}[a_{i},a_{j}](z,v)$:

$\left(\begin{array}[]{c|ccc}x\backslash y&a&b&c\\\ \hline\cr
a&\left\\{\left(a,a\right)\right\\}&\emptyset&\emptyset\\\
b&\emptyset&\left\\{\left(a,b\right),\left(a,c\right),\left(c,c\right)\right\\}&\emptyset\\\
c&\emptyset&\left\\{\left(c,a\right)\right\\}&\emptyset\end{array}\right)$ (4)

A _block_ in the selection matrix is a subset of rows $A\subseteq D$ and
columns $B\subseteq D$. We also associate with a block $(A,B)$ the
corresponding constraint $R(\vec{u})|_{x\in A,y\in B}$. A selection matrix is
a _proper block matrix_ , if there exist pairwise disjoint
$A_{1},\ldots,A_{k}\subseteq D$ and pairwise disjoint
$B_{1},\ldots,B_{k}\subseteq D$ such that for all $a_{i},a_{j}\in D$:

$\operatorname{sol}(M^{R}_{x,y}[a_{i},a_{j}])\neq\emptyset\quad\Longleftrightarrow\quad\text{there
is $\ell\in[k]$ such that $a_{i}\in A_{\ell}$ and $a_{j}\in B_{\ell}$}.$ (5)

The selection matrix in Example 3.2 is a proper block matrix with
$A_{1}=\\{a\\}$, $A_{2}=\\{b,c\\}$, $B_{1}=\\{a\\}$, $B_{2}=\\{b\\}$. We will
make use of the following alternative characterization of proper block
matrices. The simple proof is similar to [DyerR13, Lemma 1], and given in the
appendix.

A selection matrix $M^{R}_{x,y}$ is a proper block matrix if and only if it
has no $2\times 2$-submatrix with exactly one empty entry.

######  Proof 3.3.

Let $M^{R}_{x,y}$ be a proper block matrix and $A_{1},\ldots,A_{k}\subseteq
D$, $B_{1},\ldots,B_{k}\subseteq D$ be the pairwise disjoint sets provided by
the definition. Let $A_{0}:=D\setminus\bigcup_{i\in[k]}A_{i}$ and
$B_{0}:=D\setminus\bigcup_{i\in[k]}B_{i}$. Each entry of $M^{R}_{x,y}$ is now
contained in one block $(A_{i},B_{j})$ for $0\leq i\leq k$ and $0\leq j\leq
k$. A $2\times 2$-submatrix may intersect $1$, $2$ or $4$ such blocks. If it
intersects only one block, it has either $0$ or $4$ empty entries. If in
intersect two blocks, it has either $2$ or $4$ empty entries. If it intersects
$4$ blocks, at least two of them must be empty since each row and column
intersect at most one non-empty block. Thus it may have $2$, $3$, or $4$ empty
entries.

For the other direction, we must show how to find the block structure. Take
one non-empty entry and reorder the rows to $a_{1},a_{2},\ldots$ and columns
to $b_{1},b_{2},\ldots$ such that this entry is in the first column and first
row, and the first row (column) starts with $s$ ($t$) non-empty entries
followed by empty entries. Consider for all $i,j$ the $2\times 2$-submatrix
indexed by $a_{1},a_{i}$ and $b_{1},b_{j}$. Since it does not have exactly one
empty entry, we get:

  * •

If $i\leq s$ and $j\leq t$, then $M^{R}_{x,y}[a_{i},b_{j}]\neq\emptyset$.

  * •

If $i\leq s$ and $j>t$, then $M^{R}_{x,y}[a_{i},b_{j}]=\emptyset$.

  * •

If $i>s$ and $j\leq t$, then $M^{R}_{x,y}[a_{i},b_{j}]=\emptyset$.

Thus, we can choose $A_{1}=\\{a_{1},\ldots,a_{s}\\}$
$B_{1}=\\{b_{1},\ldots,b_{t}\\}$ and proceed with the submatrix on rows
$D\setminus A_{1}$ and columns $D\setminus B_{1}$ inductively.

Now we can define our central tractablility criterion for constraints that
have small ODDs, namely that any selection matrix is a proper block matrix
whose blocks are decomposable over the same variable partition that separates
$x$ and $y$.

######  Definition 3.4 (Uniform blockwise decomposability).

A constraint $R(\vec{u})$ is _uniformly blockwise decomposable in $x,y$_ if
$M^{R}_{x,y}$ is a proper block matrix with partitions $(A_{1},\ldots,A_{k})$,
$(B_{1},\ldots,B_{k})$ and there is a partition $(V,W)$ of $\tilde{u}$ with
$x\in V$ and $y\in W$ such that each block $R(\vec{u})|_{x\in A_{i},y\in
B_{i}}$ is decomposable in $(V,W)$. A constraint $R(\vec{u})$ is _uniformly
blockwise decomposable_ if it is uniformly decomposable in any pair
$x,y\in\tilde{u}$.

In the non-uniform version of blockwise decomposability, it is allowed that
the blocks are decomposable over different partitions. This property will be
used to characterize constraints having small FDD representations.

######  Definition 3.5 (Blockwise decomposability).

A constraint $R(\vec{u})$ is _blockwise decomposable in $x,y$_ if
$M^{R}_{x,y}$ is a proper block matrix with partitions $(A_{1},\ldots,A_{k})$,
$(B_{1},\ldots,B_{k})$ and for each $i\in[k]$ there are
$V_{i},W_{i}\subseteq\tilde{u}$ with $x\in V_{i}$ and $y\in V_{j}$ such that
each block $R(\vec{u})|_{x\in A_{i},y\in B_{i}}$ is decomposable in
$(V_{i},W_{j})$. A constraint $R(\vec{u})$ is _blockwise decomposable_ if it
is decomposable in any pair $x,y\in\tilde{u}$.

Note that every uniformly blockwise decomposable relation is also blockwise
decomposable. The next example illustrates that the converse does not hold.

######  Example 3.6.

Consider the 4-ary constraint relations

$\displaystyle R_{1}$
$\displaystyle:=\\{(a,a,a,a),\,(a,b,a,b),\,(b,a,b,a),\,(b,b,b,b)\\}$ (6)
$\displaystyle R_{2}$
$\displaystyle:=\\{(c,c,c,c),\,(c,d,d,c),\,(d,c,c,d),\,(d,d,d,d)\\}$ (7)
$\displaystyle R$ $\displaystyle:=R_{1}\cup R_{2}$ (8)

Then the selection matrix $M^{R}_{x,y}$ of the constraint $R(x,y,u,v)$ has two
non-empty blocks:

$M_{x,y}^{R}=\left(\begin{array}[]{c|cccc}x\backslash y&a&b&c&d\\\ \hline\cr
a&\left\\{\left(a,a\right)\right\\}&\left\\{\left(a,b\right)\right\\}&\emptyset&\emptyset\\\
b&\left\\{\left(b,a\right)\right\\}&\left\\{\left(b,b\right)\right\\}&\emptyset&\emptyset\\\
c&\emptyset&\emptyset&\left\\{\left(c,c\right)\right\\}&\left\\{\left(d,c\right)\right\\}\\\
d&\emptyset&\emptyset&\left\\{\left(d,c\right)\right\\}&\left\\{\left(d,d\right)\right\\}\end{array}\right)$
(9)

The first block $R(x,y,u,v)|_{x\in\\{a,b\\},y\in\\{a,b\\}}=R_{1}(x,y,u,v)$ is
decomposable in $\\{x,u\\}$ and $\\{y,v\\}$, while the second block
$R(x,y,u,v)|_{x\in\\{c,d\\},y\in\\{c,d\\}}=R_{2}(x,y,u,v)$ is decomposable in
$\\{x,v\\}$ and $\\{y,u\\}$. Thus, the constraint is blockwise decomposable in
$x,y$, but not uniformly blockwise decomposable.

Finally, we transfer these characterizations to relations and constraint
languages: A $k$-ary relation $R$ is (uniformly) blockwise decomposable, if
the constraint $R(x_{1},\ldots,x_{k})$ is (uniformly) blockwise decomposable
for pairwise distinct variables $x_{1},\ldots,x_{k}$. A constraint language
$\Gamma$ is (uniformly) blockwise decomposable if every relation in $\Gamma$
is (uniformly) blockwise decomposable. A constraint language $\Gamma$ is
_strongly (uniformly) blockwise decomposable_ if its co-clone
$\langle\Gamma\rangle$ is (uniformly) blockwise decomposable.

Now we are ready to formulate our main theorems. The first one states that the
strongly uniformly blockwise decomposable constraint languages are precisely
those that can be efficiently compiled to a structured representation format
(anything between ODDs and structured DNNFs).

######  Theorem 3.7.

Let $\Gamma$ be a constraint language.

  1. 1.

If $\Gamma$ is strongly uniformly blockwise decomposable, then there is a
polynomial time algorithm that constructs an ODD for a given
CSP($\Gamma$)-instance.

  2. 2.

If $\Gamma$ is not strongly uniformly blockwise decomposable, then there is a
family $(I_{n})$ of CSP($\Gamma$)-instances such that any structured DNNF for
$I_{n}$ has size $2^{\Omega(\|I_{n}\|)}$.

Our second main theorem states that the larger class of strongly blockwise
decomposable constraint languages captures CSPs that can be efficiently
compiled in an unstructured format between FDDs and DNNFs.

######  Theorem 3.8.

Let $\Gamma$ be a constraint language.

  1. 1.

If $\Gamma$ is strongly blockwise decomposable, then there is a polynomial
time algorithm that constructs an FDD for a given CSP($\Gamma$)-instance.

  2. 2.

If $\Gamma$ is not strongly blockwise decomposable, then there is a family
$(I_{n})$ of CSP($\Gamma$)-instances such that any DNNF for $I_{n}$ has size
$2^{\Omega(\|I_{n}\|)}$.

##  4 Properties of the Decomposability Notions

In this section we state important properties about (uniform) blockwise
decomposability – all omitted proofs are given in the appendix. We start by
observing that these notions are closed under projection and selection.

Let $R(\vec{u})$ be a blockwise decomposable, resp. uniformly blockwise
decomposable, constraint and let $Y\subseteq\tilde{u}$, $z\in\tilde{u}$, and
$S\subseteq D$. Then the projection $\pi_{Y}R(\vec{u})$ as well as the
selection $R(\vec{u})|_{z\in S}$ are also blockwise decomposable, resp.
uniformly blockwise decomposable.

######  Proof 4.1.

If $R(\vec{u})$ is (uniformly) blockwise decomposable consider $x,y\in Y$.
First note that each entry $M_{x,y}^{\pi_{Y}R(\vec{u})}[a_{i},b_{j}]$ is non-
empty if $M_{x,y}^{R(\vec{u})}[a_{i},b_{j}]$ is non-empty. Thus,
$M_{x,y}^{\pi_{Y}R(\vec{u})}$ is a proper block matrix with the same block
structure $(A_{1},\ldots,A_{k})$ and $(B_{1},\ldots,B_{k})$ as
$M_{x,y}^{R(\vec{u})}$. Furthermore, if a block $R(\vec{u})|_{x\in A_{i},y\in
B_{i}}$ is decomposable in $(V,W)$, then the corresponding block
$(\pi_{Y}R(\vec{u}))|_{x\in A_{i},y\in B_{i}}$ in
$M_{x,y}^{\pi_{Y}R(\vec{u})}$ is decomposable in $(V\cap Y,W\cap Y)$. It
follows that $\pi_{Y}R(\vec{u})$ is (uniformly) decomposable.

For the selection “$z\in S$” first consider the case where $x=z$ or $y=z$.
Then the selection matrix $M_{x,y}^{R(\vec{u})|_{z\in S}}$ is a submatrix of
$M_{x,y}^{R(\vec{u})}$ and hence (uniformly) blockwise decomposable if
$M_{x,y}^{R(\vec{u})}$ was (uniformly) blockwise decomposable. In case
$z\notin\\{x,y\\}$, the matrix $M_{x,y}^{R(\vec{u})|_{z\in S}}$ has the same
block structure as $M_{x,y}^{R(\vec{u})}$ and its entries decomposable w.r.t.
the same partitions. Hence $R(\vec{u})|_{z\in S}$ is also (uniformly)
blockwise decomposable w.r.t. the pair $x,y$.

If a constraint language $\Gamma$ is strongly (uniformly) blockwise
decomposable, then its individualization
$\Gamma^{\bullet}:=\Gamma\cup\big{\\{}\\{a\\}:a\in D\big{\\}}$ is also
strongly (uniformly) blockwise decomposable.

######  Proof 4.2.

Any pp-formula defining $R(\vec{x})\in\langle\Gamma^{\bullet}\rangle$ can be
rewritten as $R(\vec{x})=F(\vec{x})\land\bigwedge_{i}U_{a_{i}}(x_{i})$, where
$F(\vec{x})$ is a pp-formula over $\Gamma$. Since by assumption $F(\vec{x})$
is (uniformly) blockwise decomposable, the same holds for $R(\vec{x})$ by
repeatedly applying the selection $x_{i}=a_{i}$ and Lemma 4.

Next, we will show that blockwise decomposable relations allow for efficient
counting of solutions by making a connection to the work of Dyer and Richerby
[DyerR13]. To state their dichotomy theorem, we need the following
definitions. A constraint $R(\vec{x},\vec{y},\vec{z})$ is _balanced_ (w.r.t.
$\vec{x};\vec{y};\vec{z}$), if the $|D|^{|\vec{x}|}\times|D|^{|\vec{y}|}$
matrix $M^{\\#}_{\vec{x},\vec{y}}$ defined by
$M^{\\#}_{\vec{x},\vec{y}}[\vec{a},\vec{b}]=\big{|}\operatorname{sol}(R(\vec{x},\vec{y},\vec{z})|_{\vec{x}=\vec{a},\vec{y}=\vec{b}})\big{|}$
is a block diagonal matrix (after permuting rows/columns), where each block
has rank one. A constraint language $\Gamma$ is _strongly balanced_ if every
at least ternary pp-definable constraint is balanced.

######  Theorem 4.3 (Effective counting dichotomy [DyerR13]).

If $\Gamma$ is strongly balanced, then there is a polynomial time algorithm
that computes $|\operatorname{sol}(I)|$ for a given CSP($\Gamma$)-instance
$I$. If $\Gamma$ is not strongly balanced, then counting solutions for
CSP($\Gamma$)-instances is $\\#$P-complete. Moreover, there is a polynomial
time algorithm that decides if a given constraint language $\Gamma$ is
strongly balanced.

Our next lemma, whose proof is deferred to the appendix, connects blockwise
decomposability with strong balance and leads to a number of useful
corollaries. We sketch the proof for the case when
$R(\vec{x},\vec{y},\vec{z})$ is ternary and provide a full proof in the
appendix.

Every strongly blockwise decomposable constraint language is strongly
balanced.

Let $\Gamma$ be strongly blockwise decomposable and $R(x,y,z)$ a pp-defined
ternary constraint. Then the selection matrix $M^{R(x,y,z)}_{x,y}$ is a block
matrix, where each block $(A,B)$ is decomposable in some $(V,W)$, either
$(\\{x,z\\},\\{y\\})$ or $(\\{x\\},\\{y,z\\})$. In any case, for the
corresponding block $(A,B)$ in $M^{\\#}_{x,y}$ we have
$M^{\\#}_{x,y}[a,b]=s_{a}\cdot t_{b}$ where
$s_{a}=|\operatorname{sol}(\pi_{V}(R(x,y,z)|_{x=a,y\in B}))|$ and
$t_{b}=|\operatorname{sol}(\pi_{W}(R(x,y,z)|_{x\in A,y=b}))|$. Thus, the block
has rank 1.

To prove Lemma 4, it will be convenient to have a generalization of the
selection matrix $M^{R}_{x,y}$. So consider a relation $R$ in variables
$\vec{x},\vec{y},\vec{z}$ and domain $D$. Then $M_{\vec{x},\vec{y}}^{R}$ is
the $(|D|^{|\vec{x}|})\times(|D|^{|\vec{y}|})$-matrix whose rows are indexed
by assignments $a:\tilde{x}\rightarrow D$, whose column are indexed by the
assignments $b:\tilde{y}\rightarrow D$ and that have as entry at position
$a,b$ the constraint

$\displaystyle\\{c:\tilde{z}\rightarrow
D\mid(a,b,c)\in\operatorname{sol}(R(\vec{x},\vec{y},\vec{z}))\\}.$

We say that $R$ is blockwise set-decomposable with respect to $\vec{x}$ and
$\vec{y}$ if $M_{\vec{x},\vec{y}}^{R}$ is a proper block matrix and for every
non-empty block $B$, the selection $R|_{(\vec{x},\vec{y})\in B}$ is
decomposable such that no factor contains variables of $\vec{x}$ and
$\vec{y}$. We say that $R$ is blockwise set-decomposable if it is blockwise
set-decomposable for all choices $\vec{x},\vec{y}$ of disjoint variable sets.

######  Lemma 4.4.

Let $R$ be a relation. Then $R$ is blockwise set-decomposable if and only if
it is blockwise decomposable.

######  Proof 4.5.

If $R$ is blockwise set-decomposable, then it is by definition also blockwise
decomposable. It only remains to show the other direction. So assume that $R$
is blockwise decomposable. We proceed by induction on $|\vec{x}|+|\vec{y}|$.
If $|\vec{x}|+|\vec{y}|=1$, then $\vec{x}$ and $\vec{y}$ each consist of one
variable, so there is nothing to show.

Now assume that w.l.o.g. $|\vec{x}|>1$. Let $\vec{z}$ be the variables of $R$
not in $\vec{x}\cup\vec{y}$. We first show that for all choices of
$\vec{x},\vec{y}$ the matrix $M^{R}_{\vec{x},\vec{y}}$ is a proper block
matrix with the criterion of Lemma 3. Consider assignments
$\vec{a},\vec{b},\vec{c},\vec{d}$ such that
$R|_{\vec{x}=\vec{a},\vec{y}=\vec{c}}\neq\emptyset$,
$R|_{\vec{x}=\vec{a},\vec{y}=\vec{d}}\neq\emptyset$,
$R|_{\vec{x}=\vec{b},\vec{y}=\vec{c}}\neq\emptyset$. We have to show that
$R|_{\vec{b}=\vec{a},\vec{y}=\vec{d}}\neq\emptyset$ as well. Let $x$ be one of
the variables in $\vec{x}$ and let $\vec{x}^{\prime}$ denote the other
variables in $\vec{x}$. Let $\vec{a}^{\prime}$ and $a$ denote the restriction
of $\vec{a}$ to $\vec{x}^{\prime}$ and $x$, respectively. We have
$R|_{\vec{x}^{\prime}=\vec{a}^{\prime},\vec{y}=\vec{d}}\neq\emptyset$,
$R|_{\vec{x}^{\prime}=\vec{a}^{\prime},\vec{y}=\vec{d}}\neq\emptyset$ and
$R|_{\vec{x}^{\prime}=\vec{b}^{\prime},\vec{y}=\vec{c}}\neq\emptyset$, so by
induction
$R|_{\vec{x}^{\prime}=\vec{b}^{\prime},\vec{y}=\vec{d}}\neq\emptyset$, so in
$M^{R}_{\vec{x}^{\prime},\vec{y}}$ all four entries lie in a block $B$. By
decomposability of $B$, there are relations
$V_{\vec{a}^{\prime}},V_{\vec{b}^{\prime}},W_{\vec{c}},W_{\vec{d}}$ such that
$\pi_{\tilde{z}\cup\\{x\\}}R|_{\vec{x}^{\prime}=a^{\prime},\vec{y}=\vec{c}}=V_{\vec{a}}\times
W_{\vec{c}}$ and analogously for the other entries of
$M^{R}_{\vec{x}^{\prime},\vec{y}}$. Since
$R|_{\vec{x}=\vec{a},\vec{y}=\vec{d}}\neq\emptyset$ and
$R|_{\vec{x}=\vec{b},\vec{y}=\vec{c}}\neq\emptyset$, we have that
$a\in\pi_{x}(V_{\vec{b}}\times W_{\vec{c}})$ and
$a\in\pi_{x}(V_{\vec{a}}\times W_{\vec{d}})$ and thus also
$a\in\pi_{x}(V_{\vec{b}}\times
W_{\vec{d}})=\pi_{x}(R|_{\vec{x}^{\prime}=\vec{b}^{\prime},\vec{y}=\vec{c}})$.
It follows that $R|_{\vec{x}=\vec{a},\vec{y}=\vec{c}}\neq\emptyset$ and thus
$M^{R}_{\vec{x},\vec{y}}$ is a block matrix.

It remains to show that the blocks of $M^{R}_{\vec{x},\vec{y}}$ decompose. So
let $A$ and $B$ be the index sets of a block in the matrix. Consider again
$x\in\vec{x}$ and let the notation be as before. Let
$A^{\prime}:=\\{a|_{\vec{x}}\mid\vec{a}\in A\\}$. Then we have for all
$(\vec{a}^{\prime},\vec{c})\in A^{\prime}\times B$ that
$R|_{\vec{x}^{\prime}=\vec{a}^{\prime},\vec{y}=\vec{c}}\neq\emptyset$, so by
induction we have that for every $\vec{a}^{\prime}\in A^{\prime}$ there is a
relation $V_{a^{\prime}}$ and for every $\vec{c}\in B$ there is a relation
such that $R|_{\vec{x}^{\prime}=\vec{a},\vec{y}=\vec{x}}=V_{\vec{a}}\times
W_{\vec{b}}$. Moreover, all $V_{\vec{a}}$ are in the same variables and the
same is true for all the $W_{\vec{c}}$. If $x$ is a variable of the
$V_{\vec{a}}$, then
$R_{\vec{x}=\vec{a},\vec{y}=\vec{c}}=R|_{\vec{x}^{\prime}=\vec{a},x=a,\vec{y}=\vec{x}}=V_{\vec{a}}|_{x=a}\times
W_{\vec{b}}$ so we get the decomposition of the block in
$M^{R}_{\vec{x},\vec{y}}$ directly. Otherwise, so if $x$ is a variable of the
$W_{\vec{b}}$, we have $R_{\vec{x}=\vec{a},\vec{y}=\vec{c}}=V_{\vec{a}}\times
W_{\vec{b}}|_{x=a}=(V_{\vec{a}}\times\\{x\mapsto a\\})\times
W^{\prime}_{\vec{b}}$ where we get $W^{\prime}_{\vec{b}}$ from
$W_{\vec{b}}|_{x=a}$ by projecting away $x$. Again, we get decomposability of
the block and it follows that $R$ is blockwise set-decomposable.

We show the following connection between balance and blockwise
decomposability.

######  Lemma 4.6.

Every blockwise decomposable relation is balanced.

######  Proof 4.7.

Let $R$ be blockwise decomposable. Let $\vec{x},\vec{y}$ be variable sets. We
want to show that $\bar{M}^{R}_{\vec{x},\vec{y}}$. Let $B=A\times C$ be a
block. Since, by Lemma 4.4 the relation $R$ is blockwise set-decomposable,
every entry of $B$ can be written as
$|R_{\vec{x}=\vec{a},\vec{y}=\vec{b}}|=|V_{\bar{a}}\times W_{\bar{c}}|$ where
the $V_{a}$ and $V_{\bar{a}}$ and $W_{\bar{c}}$ are the relations given by the
decomposability of $B$. It follows directly that $B$ is a rank-$1$ matrix
which shows the lemma.

######  Proof 4.8 (Proof of Lemma 4).

To proof follows immediately from Lemma 4.6.

Let $\Gamma$ be a strongly blockwise decomposable constraint language.

  1. 1.

Given a $\Gamma$-formula $F(\vec{u})$ and a (possibly empty) partial
assignment $\alpha$, the number
$\big{|}\operatorname{sol}(F(\vec{u})|_{\alpha})\big{|}$ of solutions that
extend $\alpha$ can be computed in polynomial time.

  2. 2.

Given a pp-formula $F(\vec{u})$ over $\Gamma$ and $x,y\in\tilde{u}$, the
blocks of $M^{F(\vec{u})}_{x,y}$ can be computed in polynomial time.

  3. 3.

Given a pp-formula $F(\vec{u})$ over $\Gamma$, the indecomposable factors of
$F(\vec{u})$ can be computed in polynomial time.

Claim 1 follows immediately from the combination of Lemma 4 with Theorem 4.3
and the fact that strongly blockwise decomposable constraint languages are
closed under selection (Corollary 4). For Claim 2 let
$F(\vec{u})=\pi_{\tilde{u}}(F^{\prime}(\vec{v}))$ for some $\Gamma$-formula
$F^{\prime}(\vec{v})$. To compute the blocks of $M^{F(\vec{u})}_{x,y}$, we can
use Claim 1 to compute for every $x=a$ and $y=b$ whether
$|\operatorname{sol}(M^{F^{\prime}(\vec{v})}_{x,y}[a,b])|>0$ and hence
$M^{F(\vec{u})}_{x,y}\neq\emptyset$. Claim 3 is a bit more subtle and deferred
to the appendix.

######  Proof 4.9 (Proof of Corollary 4).

Claim 1 follows immediately from the combination of Lemma 4 with Theorem 4.3
and the fact that strongly blockwise decomposable constraint languages are
closed under selection (Corollary 4). For Claim 2 let
$F(\vec{u})=\pi_{\tilde{u}}(F^{\prime}(\vec{v}))$ for some $\Gamma$-formula
$F^{\prime}(\vec{v})$. To compute the blocks of $M^{F(\vec{u})}_{x,y}$, we can
use Claim 1 to compute for every $x=a$ and $y=b$ whether
$|\operatorname{sol}(M^{F^{\prime}(\vec{v})}_{x,y}[a,b])|>0$ and hence
$M^{F(\vec{u})}_{x,y}\neq\emptyset$.

To prove Claim 3, note that by Claim 2 we can calculate the block structure of
$M_{x,y}^{F(\vec{u})}$ for every variable pair $x,y\in\tilde{u}$. Consider the
graph $G$ with $V(G)=\tilde{u}$ and edges between $x$ and $y$ if
$M_{x,y}^{F(\vec{u})}$ has at least two non-empty blocks. If $\\{x,y\\}\in
E(G)$ for some $x$ and $y$, then $x$ and $y$ must appear in the same
indecomposable factor of ${F(\vec{u})}$. Let $C_{1},\ldots,C_{k}$ be the
connected components of $G$. All variables of one connected component must
appear in the same factor, so $\pi_{C_{i}}(F(\vec{u}))$ is indecomposable. We
claim that
${F(\vec{u})}=\pi_{C_{1}}({F(\vec{u})})\times\cdots\times\pi_{C_{k}}({F(\vec{u})})$.
It suffices to show
${F(\vec{u})}=\pi_{C}({F(\vec{u})})\times\pi_{V(G)\setminus C}({F(\vec{u})})$
for one connected component $C$, since this can be used iteratively to show
the claim. We have that for any $x\in C$ and $y\in V(G)\setminus C$, the
selection matrix $M_{x,y}^{F(\vec{u})}$ has only one block, which can be
decomposed into $(\tilde{v},\tilde{w})$, with $x\in\tilde{v}$ and
$y\in\tilde{w}$, so that

$F(\vec{u})=\pi_{\tilde{v}}(F(\vec{u}))\times\pi_{\tilde{w}}(F(\vec{u})).$

Since $x\in\tilde{v}$, no variable from the same connected component $C$ can
be in $\tilde{w}$ and therefore $\tilde{v}\supseteq C$. Since we can obtain
such a decomposition for every $x\in C$ and $y\in V(G)\setminus C$, and the
intersection of all these decompositions induces a decomposition where $C$ is
separated from any $y$, we get that
${F(\vec{u})}=\pi_{C}({F(\vec{u})})\times\pi_{V(G)\setminus C}({F(\vec{u})})$.

We close this section by stating the following property that applies only to
_uniformly_ decomposable constraints.

Let $R(\vec{u})$ be a constraint that is uniformly blockwise decomposable in
$x$ and $y$. Then there exist $\vec{v}$ and $\vec{w}$ with
$\tilde{u}=\\{x,y\\}\mathrel{\dot{\cup}}\tilde{v}\mathrel{\dot{\cup}}\tilde{w}$
such that

$\displaystyle
R(\vec{u})=\pi_{x,\tilde{v}}R(\vec{u})\wedge\pi_{y,\tilde{w}}R(\vec{u})\wedge\pi_{x,y}R(\vec{u}).$
(10)

Furthermore, if $R$ is defined by a pp-formula $F$ over a strongly uniformly
blockwise decomposable $\Gamma$, then $\vec{v}$ and $\vec{w}$ can be computed
from $F$ in polynomial time.

######  Proof 4.10.

Since $R(\vec{u})$ is uniformly blockwise decomposable in $x$ and $y$, there
exist $\vec{v}$ and $\vec{w}$ with
$\tilde{u}=\\{x,y\\}\mathrel{\dot{\cup}}\tilde{v}\mathrel{\dot{\cup}}\tilde{w}$
such that for all $a,b\in D$ we have

$\displaystyle
M^{R}_{x,y}[a,b]=\pi_{\tilde{v}}(R(\vec{u})|_{x=a})\times\pi_{\tilde{w}}(R(\vec{u})|_{y=b})\;\text{
or }\;\operatorname{sol}(M^{R}_{x,y}[a,b])=\emptyset.$ (11)

We will show (10) for this choice of $\vec{v}$ and $\vec{w}$. First, if
$\beta:\tilde{u}\to D$ satisfies $R(\vec{u})$, then by definition of
projections, we have for every $\tilde{x}\subseteq\tilde{u}$ that
$\beta|_{\tilde{x}}$ satisfies $\pi_{\tilde{x}}(R(\vec{u}))$, which yields the
containment $\subseteq$ of (10). So let
$\alpha\in\pi_{x,\tilde{v}}R(\vec{u})\wedge\pi_{y,\tilde{w}}R(\vec{u})\wedge\pi_{x,y}R(\vec{u})$.
Since $\alpha|_{\\{x,y\\}}\in\pi_{x,y}R(\vec{u})$ we get
$M_{x,y}^{R}[\alpha(x),\alpha(y)]\neq\emptyset$ and thus

$\displaystyle
M_{x,y}^{R}[\alpha(x),\alpha(y)]=\pi_{\tilde{v}}(R(\vec{u})|_{x=\alpha(x)})\times\pi_{\tilde{w}}(R(\vec{u})|_{y=\alpha(y)}).$
(12)

Now $\alpha|_{\\{x\\}\cup\tilde{v}}\in\pi_{\\{x\\}\cup\tilde{v}}(R(\vec{u}))$
implies that
$\alpha|_{\tilde{v}}\in\pi_{\tilde{v}}\left(R(\vec{u})|_{x=a}\right)$.
Analogously,
$\alpha|_{\\{y\\}\cup\tilde{w}}\in\pi_{\\{y\\}\cup\tilde{\vec{w}}}R(\vec{u})$
implies that
$\alpha|_{\tilde{w}}\in\pi_{\tilde{w}}\left(R(\vec{u})|_{y=b}\right)$. Thus we
get $\alpha|_{\tilde{v}\cup\tilde{w}}\in M_{x,y}^{R}[\alpha(x),\alpha(y)]$ and
$\alpha\in R(\vec{u})$.

It remains to show how to find $\vec{v}$ and $\vec{w}$ in polynomial time in
$\|F\|$ if given as pp-definition $F$. For every pair $a,b\in D$, we consider
the formula $F_{x=a,y=b}=F\wedge U_{a}(x)\wedge U_{b}(y)$. By Lemma 4,
$F_{x=a,y=b}$ is uniformly blockwise decomposable. By Corollary 4.3, the
indecomposable factors of $F_{x=a,y=b}$ can be computed in polynomial time.
Let $\rho_{x=a,y=b}$ be the partition of $\tilde{u}\setminus\\{x,y\\}$
according to these indecomposable factors. Let $\rho$ be the finest partition
of $\tilde{u}\setminus\\{x,y\\}$ coarser then all the $|D|^{2}$ partitions
$\rho_{x=a,y=b}$. The uniformly blockwise decomposability implies that the
variables in $\tilde{v}$ appear in a different indecomposable factors as the
variables in $\tilde{w}$, so $\rho_{x=a,y=b}$ is finer or equal to the
partition $\\{\tilde{v},\tilde{w}\\}$. This implies that $\rho$ is finer as or
equal to $\\{\tilde{v},\tilde{w}\\}$. To finish the prove of the lemma we can
take $\tilde{v}$ to be any set in $\rho$ and let
$\tilde{w}=\tilde{u}\setminus(\tilde{v}\cup\\{x,y\\})$.

##  5 Algorithms

###  5.1 Polynomial time construction of ODDs for strongly uniformly blockwise
decomposable constraint languages

The key to the efficient construction of ODD for uniformly blockwise
decomposable constraints is the following lemma, which states that any such
constraint is equivalent to a treelike conjunction of binary projections of
itself.

######  Lemma 5.1 (Tree structure lemma).

Let $R(\vec{u})$ be a constraint that is uniformly blockwise decomposable.
Then there is an undirected tree $T$ with vertex set $V(T)=\tilde{u}$ such
that

$\displaystyle R(\vec{u})=\textstyle\bigwedge_{\\{p,q\\}\in
E(T)}\pi_{\\{p,q\\}}(R(\vec{u})).$

Furthermore, $T$ can be calculated in polynomial time in $\|F\|$, if $R$ is
uniformly blockwise decomposable and given as pp-formula $F$.

Note that from Lemma 5.1 is follows in particular that any uniformly
decomposable constraint is a conjunction of binary constraints. Thus, it
follows from Theorem 3.7, our main result for ODD-representations, that any
constraint language that allows efficient ODD-representations can essentially
only consist of binary constraints. Hence, for example affine constraints, for
which it is known that they allow efficient counting [CreignouH96], are hard
in our setting.

######  Proof 5.2 (Proof of Lemma 5.1).

We first fix $x$ and $y$ arbitrarily and apply Lemma 4 to obtain a tri-
partition ($\tilde{v}$, $\\{x,y\\}$, $\tilde{w}$) of $\tilde{u}$ such that
$R(\vec{u})=\pi_{x,\tilde{v}}(R(\vec{u}))\wedge\pi_{x,y}(R(\vec{u}))\wedge\pi_{y,\tilde{w}}(R(\vec{u}))$.
We add the edge $\\{x,y\\}$ to $T$. By Lemma 4,
$\pi_{x,\tilde{v}}(R(\vec{u}))$ and $\pi_{y,\tilde{w}}(R(\vec{u}))$ are
uniformly blockwise decomposable, so Lemma 4 can be recursively applied on
both projections. For (say) $\pi_{x,\vec{v}}(R(\vec{u}))$ we fix $x$, choose
an arbitrary $z\in\tilde{v}$, apply Lemma 4, and add the edge $\\{x,z\\}$ to
$T$. Continuing this construction recursively until no projections with more
than two variables are left yields the desired result.

From this tree structure we will construct small ODDs by starting with a
centroid, i. e., a variable whose removal splits the tree into connected
components of at most $n/2$ vertices each. From the tree structure lemma it
follows that we can handle the (projection on the) subtrees independently. A
recursive application of this idea leads to an ODD of size $O(n^{\log|D|+1})$.

######  Proof 5.3 (Proof of part 1 in Theorem 3.7).

Let $I$ be a CSP($\Gamma$)-instance and $F_{I}(\vec{u})$ the corresponding
$\Gamma$-formula. By Lemma 5.1 we can compute a tree $T$ such that
$F_{I}(\vec{u})=\bigwedge_{\\{p,q\\}\in E(T)}\pi_{\\{p,q\\}}(F_{I}(\vec{u}))$.
By Corollary 4.1 we can explicitly compute, for each $\\{p,q\\}\in E(T)$, a
binary relation $R_{\\{p,q\\}}\subseteq D^{2}$ such that
$R_{\\{p,q\\}}(p,q)=\pi_{\\{p,q\\}}(F_{I}(\vec{u}))$. Now we define the
formula $F_{T}(\vec{u})=\bigwedge_{\\{p,q\\}\in E(T)}R_{\\{p,q\\}}(p,q)$ and
note that
$\operatorname{sol}(F_{T}(\vec{u}))=\operatorname{sol}(F_{I}(\vec{u}))$. It
remains to show that such tree-CSP instances can be efficiently compiled to
ODDs. This follows from the following inductive claim, where for technical
reasons we also add unary constraints $U_{D_{v}}(v)$ for each vertex $v$
(setting $D_{v}:=D$ implies the theorem).

Let $T$ be a tree on $n$ vertices and $F_{T}(\vec{u})=\bigwedge_{\\{v,w\\}\in
E(T)}R_{\\{v,w\\}}(v,w)\land\bigwedge_{v\in\tilde{u}}U_{D_{v}}(v)$ be a
formula. Then there is an order $<$, depending only on $T$, such that an ODD<
of size at most $f(n):=n|D|^{\log(n)}$ deciding $F_{T}(\vec{u})$ can be
computed in $n^{O(1)}$.

We proof the claim by induction on $n$ and the start $n=1$ is trivial. If
$n\geq 2$ let $z$ be a centroid in this tree, that is a node whose removal
splits the tree into $\ell\geq 1$ connected components $T_{1}$,…, $T_{\ell}$
of at most $n/2$ vertices each. Let $\vec{v}_{1}$, …, $\vec{v}_{\ell}$ be
vectors of the variables in these components, so ($\\{z\\}$, $\tilde{v}_{1}$,
…, $\tilde{v}_{\ell}$) partitions $\tilde{u}$. Let $x_{i}\in V(T_{i})$ be the
neighbors of $z$ in $T$. We want to branch on $z$ and recurse on the connected
components $T_{i}$. To this end, for each assignment $z\mapsto a$ we remove
for each neighbor $x_{i}$ those values that cannot be extended to $z\mapsto
a$. That is, $D^{a}_{x_{i}}:=\\{b\colon\\{x_{i}\mapsto b,z\mapsto
a\\}\in\operatorname{sol}(U_{D_{x_{i}}}(x_{i})\land
R_{\\{x_{i},z\\}}(x_{i},z)\land U_{D_{z}}(z))\\}$. Now we let
$F^{a}_{i}(\vec{v}_{i}):=\bigwedge_{\\{v,w\\}\in
E(T_{i})}R_{\\{v,w\\}}(v,w)\land\bigwedge_{v\in\tilde{v}_{i}\setminus\\{x_{i}\\}}U_{D_{v}}(v)\land
U_{D^{a}_{x_{i}}}(x_{i})$ and observe that

$\operatorname{sol}(F_{T}(\vec{u}))=\dot{\bigcup}_{a\in
D}\operatorname{sol}(U_{a}(z)\times F^{a}_{1}(\vec{v}_{1})\times\cdots\times
F^{a}_{\ell}(\vec{v}_{\ell})).$ (13)

By induction assumption, for each $i\in[\ell]$ there is an order $<_{i}$ of
$\tilde{v}_{i}$ such that each $F^{a}_{i}(\vec{v}_{i})$ has an
ODD${}^{a}_{<_{i}}$ of size $f(n_{i})$ for $n_{i}:=|\tilde{v}_{i}|$. Now we
start our ODD for $F_{T}(\vec{u})$ with branching on $z$ followed by the
sequential combination of ODD${}^{a}_{<_{1}}$, …, ODD${}^{a}_{<_{\ell}}$ for
each assignment $a\in D$ to $z$. This completes the inductive construction.
Since its size is bounded by $1+|D|\sum_{i\in[\ell]}f(n_{i})$, the following
easy estimations finish the proof of the claim (recall that
$\sum_{i\in[\ell]}n_{i}=n-1$):
$1+|D|\textstyle\sum_{i\in[\ell]}f(n_{i})\;\leq\;1+|D|\textstyle\sum_{i\in[\ell]}n_{i}|D|^{\log(n/2)}=1+|D|^{\log(n)}(n-1)\;\leq\;n|D|^{\log(n)}$

###  5.2 Polynomial size FDDs for strongly blockwise decomposable constraint
languages

For blockwise decomposable constraints that are _not_ uniformly blockwise
decomposable, a good variable order may depend on the values assigned to
variables that are already chosen, so it is not surprising that the tree
approach for ODDs does not work in this setting.

For the construction of the FDD, we first compute the indecomposable factors
(this can be done by Corollary 4.3 and treat them independently. This, of
course, could have also been done for the ODD construction. The key point now
is how we treat the indecomposable factors: every selection matrix
$M^{R}_{x,y}$ for a (blockwise decomposable) indecomposable constraint
necessarily has two non-empty blocks. But then every row $x=a$ must have at
least one empty entry $\operatorname{sol}(M^{R}_{x,y}[a,b])=\emptyset$. This
in turn implies that, once we have chosen $x=a$, we can exclude $b$ as a
possible value for $y$! As we have chosen $y$ arbitrarily, this also applies
to any other variable (maybe with a different domain element $b$). So the set
of possible values for every variable shrinks by one and since the domain is
finite, this cannot happen too often. Algorithm 1 formalizes this recursive
idea. To bound the runtime of this algorithm, we analyze the size of the
recursion tree; the details are found in the appendix.

1:Input: $\Gamma$-formula $F(x_{1},\ldots,x_{n})$ for strongly blockwise
decomposable $\Gamma$ over domain $D$.

2:Output: An FDD deciding $F(x_{1},\ldots,x_{n})$.

3:Initialize variable domains $D_{x_{i}}\leftarrow D$ for $i=1,\ldots,n$.

4:return ConstructFDD($F(x_{1},\ldots,x_{n})$; $D_{x_{1}}$,…,$D_{x_{n}}$)

5:

6:procedure ConstructFDD($R(x_{1},\ldots,x_{n})$; $D_{x_{1}}$,…,$D_{x_{n}}$)

7: $R(x_{1},\ldots,x_{n})\leftarrow
R(x_{1},\ldots,x_{n})\land\bigwedge_{i\in[n]}U_{D_{x_{i}}}(x_{i})$

8: if $n=1$ then

9: return 1-node FDD deciding $R(x_{1})$, branching on all values $D_{x_{1}}$.

10: Compute the indecomposable factors $R_{1}(\vec{u}_{1})$, …,
$R_{m}(\vec{u}_{m})$ of $R(x_{1},\ldots,x_{n})$.

11: if $m\geq 2$ then

12: for $i=1\ldots m$ do FDD${}_{i}\leftarrow$
ConstructFDD($R_{1}(\vec{u}_{1})$; $D_{y}$ for $y\in\tilde{u}_{i}$)

13: return Sequential composition of FDD1, …, FDDm

14: else

15: Introduce branching node for $x_{1}$.

16: for $a\in D_{x_{1}}$ do

17: for $i=2,\ldots,n$ do

18: for $b\in D_{x_{i}}$ do

19: if $\operatorname{sol}(M^{R}_{x_{1},x_{i}}[a,b])=\emptyset$ then

20: $D_{x_{i}}\leftarrow D_{x_{i}}\setminus\\{b\\}$ $\triangleright$ This
happens for at least one $b\in D_{x_{i}}$.

21:
$S_{a}(x_{2},\ldots,x_{n})\leftarrow\pi_{{x_{2},\ldots,x_{n}}}(R(x_{1},\ldots,x_{n})|_{x_{1}=a})$

22: FDD${}^{a}\leftarrow$ ConstructFDD($S_{a}(x_{2},\ldots,x_{n})$;
$D_{x_{2}}$,…,$D_{x_{n}}$)

23: Connect $x\stackrel{{\scriptstyle a}}{{\rightarrow}}$ FDDa for all $a\in
D_{x_{1}}$ and return resulting FDD

Algorithm 1 FDD construction algorithm

######  Proof 5.4 (Proof of part 1 in Theorem 3.8).

The algorithm is formalized in Algorithm 1. It is straightforward to verify
that this algorithm computes an FDD that decides $F(x_{1},\ldots,x_{n})$. It
remains to discuss the size of the FDD and the running time. First note that
the decomposition into indecomposable factors (Line 10) can be computed in
polynomial time by Corollary 4.3. Moreover, (non-)emptiness of the entries of
the selection matrices (Line 19) can be tested in polynomial time by Corollary
4.1. Hence, every call has only polynomial computation overhead and we proceed
to bound the total number of recursive calls.

To this end, let us bound the size of the recursion tree, starting by bounding
its depth. As discussed above, the crucial point is that each considered
selection matrix $M^{R}_{x_{1},x_{i}}$ in Line 19 has at least two blocks,
otherwise, the relation would have been decomposable, because by definition of
blockwise decomposability every block of $M^{R}_{x_{1},x_{2}}$ is
decomposable. Therefore, the test for empty entries will succeed at least once
and each considered variable domain shrinks. Therefore, in every root-leaf-
path in the recursion tree, there are at most $|D|$ recursive in Line 22.
Moreover, on such a path there cannot be two consecutive calls from Line 12,
because we decompose into indecomposable factors before any such call. It
follows that the recursion tree has depth at most $2|D|+1$.

Let the height $h_{v}$ of a node $v$ in the recursion tree be the distance to
the furthest leaf in the subtree below $v$. Let $n_{v}$ be the number of
variables of the constraint in that call. We claim that the number of leaves
below $v$ is at most $|D|^{h_{v}}n_{v}$. We show this by induction on $h_{v}$.
If $h_{v}=0$, then $v$ is a leaf, so we make no further recursive calls. This
only happens if $n_{v}=1$ and the claim is true. Now consider $h_{v}>0$. Let
$v_{1},\ldots,v_{r}$ be the children of $v$. If in $v$ we make a recursive
call as in Line 12, then $n_{v_{1}}+\ldots+n_{v_{r}}=n_{v}$. Also for all
$v_{i}$ we have $h_{v_{i}}<h_{v}$ and the number of leaves below $v$ is
bounded by $\sum_{i\in[r]}n_{i}|D|^{h_{i}}\leq
d^{h_{v}}\sum_{i\in[r]}n_{i}=|D|^{h_{v}}n$. If in $v$ we make a recursive call
in Line 22, then we know that $r\leq|D|$, because we make at most $|D|$ calls.
Moreover, we have again that $h_{v_{i}}<h_{v}$, so the number of leaves below
$v$ is bounded by $\sum_{i\in[r]}n_{v_{i}}|D|^{v_{i}}\leq n_{v}|D|^{h_{v}}$
which completes the induction and thus proves the claim.

It follows that the recursion tree of the algorithm has at most
$n|D|^{2|D|+1}$ leaves and thus at most $2n|D|^{2|D|+1}$ nodes. Since we add
at most one FDD-node per recursive call, this is also a bound for the size of
the computed FDD.

##  6 Lower Bounds

In this section, we will prove the lower bounds of Theorem 3.7 and Theorem
3.8. In the proofs, we will use the approach developed in [BovaCMS16] that
makes a connection between DNNF size and rectangle covers. We will use the
following variant:

Let $O$ be a DNNF of size $s$ representing a constraint $R(\vec{x})$ and let
$Z\subseteq\tilde{x}$. Then there is a $Z$-balanced rectangle cover of $f$ is
size $s$. Moreover, if $O$ is structured, then the rectangles in the cover are
all with respect to the same variable partition. The proof of Lemma 6 is very
similar to existing proofs in [BovaCMS16], so we defer it to the appendix.

###  6.1 Proof of Lemma 6

In the proof of Lemma 6, we will again use the concept of proof trees, see
Appendix 2. The idea of the proof of Lemma 6 is to partition $\mathcal{T}(O)$
in the representation (1), guided by the circuit $O$. To this end, we
introduce some more notation. Let, for every gate $v$, $\mathcal{T}(v,O)$
denote the set of proof trees of $O$ that contain $v$. Moreover, let
$\mathrm{var}(O)$ denote the variables appearing in $O$ and
$\mathrm{var}(v,O)$ the variables that appear in $O$ below the gate $v$.
Finally, let $S(v,O):=\bigcup_{T\in\mathcal{(}v,O)}S(T)$.

######  Claim 1.

$S(v,O)$ is a rectangle w.r.t.
$(\mathrm{var}(v,O),\mathrm{var}(O)\setminus\mathrm{var}(v,O))$.

######  Proof 6.1.

Every proof tree in $\mathcal{T}(v,O)$ can be partitioned into a part below
$v$ and the rest. Moreover, any such proof trees $T_{1},T_{2}$ can be combined
by combining the part below $v$ from $T_{1}$ and the rest from $T_{2}$. The
claim follows directly from this observation.

With Claim 1, we only have to choose the right gates of $O$ to partition
$\mathcal{T}(O)$ to prove Lemma 6. To this end, we construct an initially
empty rectangle cover $\mathcal{R}$ iteratively: while $O$ still captures an
assignment $a$, choose a proof tree $T$ capturing $a$ (which is guaranteed to
exist by (1)). By descending in $T$, choose a gate $v$ such that
$\mathrm{var}(v,O)$ contains between one third and two thirds of the variables
in $Z$222There is a small edge case here in which $O$ does not contain a third
of the variables in $Z$. In that case, we simply take $S(O)$ as a rectangle,
balancing it by adding the non-appearing variables appropriately.. Add
$S(v,O)$ to $\mathcal{R}$, delete $v$ from $O$ and repeat the process. When
the iteration stops, we have by Claim 1 and the choice of $v$ constructed a
set $\mathcal{R}$ of $Z$-balanced rectangle covers. Moreover,
$\bigcup_{\mathfrak{r}\in\mathcal{R}}S(\mathfrak{r})\subseteq S(O)$ by
construction. Finally, since in the end $O$ does not capture any assignments
anymore, every assignment $a$ initially captured must have been computed by
one of the proof trees of $O$ that got destroyed by deleting one of its gates
$v$. Thus $a\in S(v,O)\in\mathcal{R}$ and we have

$\displaystyle S(O)=\bigcup_{\mathfrak{r}\in\mathcal{R}}S(\mathfrak{r}),$

which shows the claim of Lemma 6 for the unstructured case.

If $O$ is structured, we choose the vertices $v$ in the iteration slightly
differently. Let $\mathcal{T}$ be the v-tree of $O$. Then we can choose a
vertex $v^{*}$ in $\mathcal{T}$ that has between one and two thirds of the
vertices in $Z$ as labels on leaves below $v^{*}$. Let $X_{\downarrow}$ be the
variable in $\mathcal{T}$ below $v$ and let $X_{\uparrow}$ be the rest of the
variables. Now in the construction of $\mathcal{R}$, in the proof tree $T$ we
can find a gate $v$ below which there are only variables in $X_{\downarrow}$
and which is closest to the root with this property. Then, by Claim 1,
$S(v,O)$ is a rectangle w.r.t. $(X_{\downarrow},X_{\uparrow})$ and thus in
particular $Z$-balanced. Since all rectangles we choose this way are with
respect to the same partition $(X_{\downarrow},X_{\uparrow})$ which depends
only on $\mathcal{T}$, the rest of the proof follows as for the unstructured
case.

###  6.2 Lower Bound for DNNF

In this Section, we show the lower bound for Theorem 3.8 which we reformulate
here.

######  Proposition 6.2.

Let $\Gamma$ be a constraint language that is not strongly blockwise
decomposable. Then there $\Gamma$-formulas $F_{n}$ of size $\Theta(n)$ and
$\varepsilon>0$ such that any $DNNF$ for $F_{n}$ has size at least
$2^{\varepsilon\left\|F_{n}\right\|}$.

In the remainder of this section, we show Proposition 6.2, splitting the proof
into two cases. First, we consider the case where $M_{x,y}^{R}$ is not a
proper block matrix.

######  Lemma 6.3.

Let $R(x,y,\vec{z})$ be a constraint such that $M_{x,y}^{R}$ is not a proper
block matrix. Then there is a family of $\\{R\\}$-formulas $F_{n}$ and
$\varepsilon>0$ such that any $DNNF$ for $F_{n}$ has size at least
$2^{\varepsilon\left\|F_{n}\right\|}$.

In the proof of Lemma 6.3, we will use a specific family of graphs. We remind
the reader that a matching is a set of edges in a graph that do not share any
end-points. The matching is induced if the graph induced by the end-points of
the matching contains exactly the edges of the matching.

######  Lemma 6.4.

There is an integer $d$ and a constant $\varepsilon>0$ such that there is an
infinite family $(G_{n})$ of $d$-regular, bipartite graphs such that for each
set $X\subseteq V(G_{n})$ with $|X|\leq n=|V(G)|/2$ there is an induced
matching of size at least $\varepsilon|X|$ in which each edge has exactly one
endpoint in $X$

###  6.3 Bipartite graphs with large independent matchings over every cut

In this appendix, we will show how to prove Lemma 6.4. The construction is
based on expander graphs in a rather straightforward way, but since we have
not found an explicit reference, we give it here for completeness. We start
with some definitions.

A graph $G$ is a $(k,A)$ vertex expander if for all sets $S$ of at most
$k|V(G)|$ vertices, the neighborhood $N(S)=\\{v\in V(G)\setminus S\mid\exists
u\in S,uv\in E\\}$ has size at least $A|S|$.

We use the following results which can readily be proved by the probabilistic
method.

######  Theorem 6.5.

There is a constant $d$ such that there are $d$-regular $(1/2,5/4)$ vertex
expanders for infinitely many sizes of vertex sets.

Note that the constants $1/2$ and $5/4$ are completely arbitrary.

We now use a construction called the double cover construction: Given a graph
$G=(V,E)$, construct a bipartite graph $G^{\prime}$ with the vertex set
$V^{\prime}=\\{(v,0),(v,1)\mid v\in V\\}$ and the edge set
$\\{(v,i),(u,1-i)\mid i\in\\{0,1\\},uv\in E\\}$.

######  Claim 2.

If $G$ is a $(1/2,5/4)$ vertex expander, then $G^{\prime}$ is a $(1/2,1/8)$
vertex expander.

######  Proof 6.6.

Let $n$ be the number of vertices in $G$. Consider a set $S$ of at most $n$
vertices in $G^{\prime}$. First assume that $S$ has at least $n/2$ vertices in
one color class. Then, by definition of expansion and $G^{\prime}$, there must
be at least $5/4\cdot n/2=5/8n$ neighbors of $S$ in the other color class.
Since $S$ has at most $n/2$ vertices in that color class, $S$ must have at
least $1/8n$ neighbors not in $S$.

Now assume that in each color class $S$ has at most $n/2$ vertices. Pick the
color class in which $S$ has more vertices and call this vertex set
$S^{\prime}$. Then $S^{\prime}$ has at least $5/4|S^{\prime}|$ neighbors in
the other color class. Since there are at most $|S^{\prime}|$ vertices of $S$
in that color class, it follows that $S^{\prime}$ has at least
$1/4|S^{\prime}|$ neighbors not in $S$ and thus the same is true for $S$. But
clearly $|S^{\prime}|\geq|S|/2$ and thus the claim follows.

######  Corollary 6.7.

There is a constant $d$ such that there are $d$-regular bipartite $(1/2,1/8)$
vertex expanders with $n$ vertices in every color class for infinitely values
$n$.

The class of graphs in Corollary 6.7 will be the class of graphs for Lemma
6.4. We now construct the distant matchings. To this end, consider a graph
$G=(V,E)$ from this class and a set $S$ of vertices of size at most $n/2$.
First construct a matching between $S$ and $V\setminus S$. Since $S$ has
$1/8|S|$ neighbors outside of $S$ and every vertex had degree at most $d$, one
can greedily find such a matching of size $\frac{|S|}{16d}$. In a second step,
we choose an induced matching out of this matching greedily. Since every edge
has at most $O(d^{2})$ edges at distance $2$, this yields an induced matching
of size $|V|/O(d^{3})$ which completes the proof.

######  Proof 6.8 (Proof of Lemma 6.3).

If $M_{x,y}^{R}$ is not a proper block matrix, then, by Lemma 3, the matrix
$M_{x,y}^{R}$ has a $2\times 2$-submatrix with exactly three non-empty
entries. So let $a,b,c,d\in D$ such that $M_{x,y}^{R}(b,d)=\emptyset$ and
$M_{x,y}^{R}(a,c)$, $M_{x,y}^{R}(a,d)$ and $M_{x,y}^{R}(b,c)$ are all non-
empty.

We describe a construction that to every bipartite graph $G=(A,B,E)$ gives a
formula $F(G)$ as follows: for every vertex $u\in A$, we introduce a variable
$x_{u}$ and for every vertex $v\in B$ we introduce a variable $x_{v}$. Then,
for every edge $e=uv\in E$ where $u\in A$ and $v\in V$, we add a constraint
$R(x_{u},x_{v},\vec{z}_{e})$ where $\vec{z}_{e}$ consists of variables only
used in this constraint. We fix the notation $X_{A}:=\\{x_{v}\mid v\in A\\}$,
$X_{B}:=\\{x_{v}\mid v\in B\\}$ and $X:=X_{A}\cup X_{B}$.

Let $(F_{n})$ be the family of formulas defined by $F_{n}=F(G_{n})$ where
$(G_{n})$ is the family from Lemma 6.4. Clearly,
$\|F_{n}\|=\Theta(|E(G_{n})|)=\Theta(n)$, as required. Fix $n$ for the
remainder of the proof. Let $F^{\prime}_{n}$ be the formula we get from
$F_{n}$ by restricting all variables $x_{u}\in X_{A}$ to $\\{a,b\\}$ and all
variables $x_{v}\in X_{B}$ to $\\{c,d\\}$ by adding some unary constraints.
Let $\mathcal{R}$ be an $X$-balanced rectangle cover of $F^{\prime}_{n}$. We
claim that the size of $\mathcal{R}$ is at least $2^{\varepsilon^{\prime}n}$,
where

$\varepsilon^{\prime}=\frac{1}{3}\cdot\varepsilon\cdot\log_{2}\left(1+\frac{1}{2^{d+1}|R|^{d^{2}}}\right)$

and $d$ is the degree of $G_{n}$. To prove this, we first show that for every
$\mathfrak{r}\in\mathcal{R}$,
$2^{\varepsilon^{\prime}|X|}\cdot|\operatorname{sol}(\mathfrak{r})|\leq|\operatorname{sol}(F^{\prime}_{n})|.$
So let
$\mathfrak{r}(\vec{v},\vec{w})=\mathfrak{r}_{1}(\vec{v})\times\mathfrak{r}_{2}(\vec{w})\in\mathcal{R}$.
Since $\mathfrak{r}$ is an $X$-balanced rectangle, we may assume
$|X|/3\leq|\vec{v}\cap V|\leq 2|X|/3$. By choice of $G_{n}$, we have that
there is an induced matching $\mathcal{M}$ in $G_{n}$ of size at least
$\varepsilon|X|/3$ consisting of edges that have one endpoint corresponding to
a variable in $\tilde{v}$ and one endpoint corresponding to a variable in
$\tilde{w}$. Consider an edge $e=uv\in\mathcal{M}$. Assume that
$x_{u}\in\tilde{v}$ and $x_{v}\in\tilde{w}$. Since we have
$\mathfrak{r}(\vec{v},\vec{w})=\mathfrak{r}(\vec{v})\times\mathfrak{r}(\vec{w})$,
we get

$\displaystyle\pi_{e}\mathfrak{r}(\vec{v},\vec{w})$
$\displaystyle=\pi_{\tilde{v}\cap e}(r(\vec{v}))\times\pi_{\tilde{w}\cap
e}(r(\vec{w})).$

By construction
$\pi_{e}\mathfrak{r}(\vec{v},\vec{w})\subseteq\\{(a,c),(a,d),(b,c)\\}$, so it
follows that either
$\pi_{e}\mathfrak{r}(\vec{v},\vec{w})\subseteq\\{(a,c),(a,d)\\}=\\{a\\}\times\\{c,d\\}$
or
$\pi_{e}\mathfrak{r}(\vec{v},\vec{w})\subseteq\\{(a,c),(b,c)\\}=\\{a,b\\}\times\\{c\\}$.
Assume w.l.o.g. that $\\{b,c\\}\notin\pi_{e}r(\vec{v},\vec{w})$ (the other
case can be treated analogously). It follows that for each solution
$\beta\in\operatorname{sol}(r)$, we get a solution
$q(\beta)\in\operatorname{sol}(F_{n})\backslash\operatorname{sol}(\mathfrak{r}(\vec{v},\vec{w}))$
by setting

  * •

$q(\beta)(x_{u}):=b$,

  * •

For all $x_{\ell}\in N(x_{u})$, we set $q(\beta)(x_{\ell}):=c$,

  * •

For all $x_{\ell}\in N(x_{u})$ and all $x_{m}\in N(y_{\ell})$ we set
$q(\beta)(\vec{z}_{m\ell}):=\vec{g}$ where $\vec{g}$ is such that
$(b,c,\vec{g})\in R$.

Note that values $\vec{g}$ exists because $M_{x,y}^{R}(b,c)$ is non-empty.
Observe that for two different solutions $\beta$ and $\beta^{\prime}$ the
solutions $q(\beta)$ and $q(\beta^{\prime})$ may be the same. However, we can
bound the number $\left|q^{-1}(q(\beta))\right|$, giving a lower bound on the
set of solutions not in $r$. To this end, suppose that
$q(\beta)=q(\beta^{\prime})$. Since $q$ only changes the values of $x_{u}$,
exactly $d$ $x_{\ell}$-variables and at most $d^{2}$ vectors of
$\vec{z}$-variables (the two latter bounds come from the degree bounds on
$G_{n}$), $q(\beta)=q(\beta^{\prime})$ implies that $\beta$ and
$\beta^{\prime}$ coincide on all other variables. This implies

$\left|q^{-1}(q(\beta))\right|\leq 2^{d+1}|R|^{d^{2}},$

because there are only that many possibilities for the variables that $q$
might change. By considering $\\{x_{u},y_{v}\\}$, we have shown that

$|\operatorname{sol}(F_{n})|\geq|\operatorname{sol}(r)|+\frac{1}{2^{d+1}|R|^{d^{2}}}|\operatorname{sol}(r)|.$

So we have constructed $\frac{|\operatorname{sol}(r)|}{2^{d+1}|R|^{d^{2}}}$
solutions not in $r$. Now we consider not only one edge but all possible
subsets $I$ of edges in $\mathcal{M}$: for a solution
$\beta\in\operatorname{sol}(\mathfrak{r}(\vec{v},\vec{w})$, the assignment
$q_{I}(\beta)$ is constructed as the $q$ above, but for all edges $e\in I$.
Reasoning as above, we get

$\left|q_{I}^{-1}(q_{I}(\beta))\right|\leq\left(2^{d+1}|R|^{d^{2}}\right)^{|I|}.$

It is immediate to see that $q_{I}(\beta)\neq q_{I^{\prime}}(\beta)$ for
$I\neq I^{\prime}$. Thus we get

$\displaystyle|\operatorname{sol}(F^{\prime}_{n})|$
$\displaystyle\geq\sum_{m=0}^{\frac{1}{3}\varepsilon|X|}\binom{\frac{1}{3}\varepsilon|X|}{m}\left(\frac{1}{2^{d+1}|R|^{d^{2}}}\right)^{m}|\operatorname{sol}(r)|$
$\displaystyle=\left(1+\frac{1}{2^{d+1}|R|^{d^{2}}}\right)^{\frac{1}{3}\varepsilon|X|}|\operatorname{sol}(r)|=2^{\varepsilon^{\prime}n}|\operatorname{sol}(r)|.$

It follows that every $X$-balanced rectangle cover has to have a size of at
least $2^{\varepsilon^{\prime}|X|}$. With Lemma 6 and Lemma 2 it follows that
any DNNF for $F_{n}$ has to have a size of at least
$2^{\varepsilon^{\prime}n}$.

Now we consider the case that $M_{x,y}^{R}$ is a proper block matrix, but $R$
is not blockwise decomposable in some pair of variables $x,y$.

Let $R(x,y,\vec{z})$ be a relation such that $M_{x,y}^{R}$ is a proper block
matrix but $R(x,y,\vec{z})$ in not blockwise decomposable in $x$ and $y$. Then
there is a family of formulas $F_{n}$ and $\varepsilon>0$ such that a $DNNF$
for $F_{n}$ needs to have a size of at least $2^{\varepsilon\|F_{n}\|}$. The
proof of Lemma 6.3 is a slight variant of that of Lemma 6.3 and we thus give
it in the appendix.

######  Proof 6.9.

The proof follows the same ideas as that of Lemma 6.3, so we state only the
differences. If $M_{x,y}^{R}$ is a proper block matrix but $R$ is not
blockwise decomposable in $x$ and $y$, there is a block $B=D_{x}\times D_{y}$
such that $R(x,y,\vec{z})_{(x,y)\in B}$ is not decomposable, in such a way
that $x$ and $y$ appear in different factors. This implies that if
$\vec{z}=\vec{v}\dot{\cup}\vec{w}$, $V\subseteq\pi_{x,\vec{v}}R(x,y,\vec{z})$
and $W\subseteq\pi_{y,\vec{w}}R(x,y,\vec{z})$, then $V\times W\subsetneq R$.
For one edge $e=\\{x_{i},y_{j}\\}\in\mathcal{M}$, the projection onto
$\mathfrak{r}$ is of this form $V\times W$, so there must exist
$(a,b,\vec{c})\in R$ and not in $\pi_{e}\mathfrak{r}$. This $(a,b,\vec{c})$ is
used for the edge $e$ to construct solutions in
$sol(F_{n})\setminus\mathfrak{r}$. Since $B$ is a block, we define $q(\beta)$
as follows:

  * •

$q(\beta)(x_{u}):=a$, $q(\beta)(x_{v}):=b$

  * •

For all $x_{\ell}\in N(x_{v})$ we set $q(\beta)(\vec{z}_{\ell v}):=\vec{g}$
such that $(\beta(x_{\ell}),b,\vec{g})\in R$.

  * •

For all $x_{\ell}\in N(x_{u})$ we set $q(\beta)(\vec{z}_{u\ell}):=\vec{g}$
such that $R(a,\beta(x_{\ell}),\vec{g})$.

It follows that we can bound the number $q^{-1}_{I}(q_{I}(\beta))$ of a
solution $\beta$ by

$q^{-1}_{I}(q_{I}(\beta))\leq\left(|D_{x}||D_{y}||R|^{2k-1}\right)^{|I|}$

so we get:

$\varepsilon=\frac{1}{3}\cdot\varepsilon^{\prime}\cdot\log_{2}\left(1+\frac{1}{|D_{x}||D_{y}||R|^{2k-1}}\right).$

The rest of the proof is unchanged.

We now have everything in place to prove Proposition 6.2.

######  Proof 6.10 (Proof of Proposition 6.2).

Since $\Gamma$ is not strongly blockwise decomposable, there is a relation
$R\in\langle\Gamma\rangle$ that is not blockwise decomposable in $x$ and $y$.
Then, by definition of co-clones and Lemma 4, there is a $\Gamma$-formula that
defines $R$. If there are variables $x,y\in\tilde{x}$ such that $M_{x,y}^{R}$
is not a proper block matrix, then we can apply Lemma 6.3 to get $R$-formulas
that require exponential size DNNF. Then by substituting all occurrences of
$R$ in these formula by the $\Gamma$-formula defining $R$, we get the required
hard $\Gamma$-formulas. If all $M_{x,y}^{R}$ are proper block matrices, then
there are variables $x,y$ such that $M_{x,y}^{R}$ is not blockwise
decomposable. Using Lemma 6.3 and reasoning as before, then completes the
proof.

###  6.4 Lower Bound for structured DNNF

In this section, we prove the lower bound of Theorem 3.7 which we formulate
here again.

######  Proposition 6.11.

Let $\Gamma$ be a constraint language that is not strongly uniformly blockwise
decomposable. Then there $\Gamma$-formulas $F_{n}$ of size $Theta(n)$ and
$\varepsilon>0$ such that any structured $DNNF$ for $F_{n}$ has size at least
$2^{\varepsilon\left\|F_{n}\right\|}$.

Note that for all constraint languages that are not strongly blockwise
decomposable, the result follows directly from Proposition 6.2, so we only
have to consider constraint languages which are strongly blockwise
decomposable but not strongly uniformly blockwise decomposable. We start with
a simple observation.

Let $\mathfrak{r}(\vec{x},\vec{y})$ be a rectangle with respect to the
partition $(\tilde{x},\tilde{y})$. Let $Z\subseteq\tilde{x}\cup\tilde{y}$,
then $\pi_{Z}(\mathfrak{r}(\tilde{x},\tilde{y}))$ is a rectangle with respect
to the partition $(\tilde{x}\cap Z,\tilde{y}\cap Z)$.

We start our proof of Proposition 6.11 by considering a special case.

######  Lemma 6.12.

Let $R(x,y,\vec{z})$ be a constraint such that there are two assignments
$a,b\in\operatorname{sol}(R)$ such that for every partition
$\tilde{z}_{1},\tilde{z}_{2}$ of $\tilde{z}$ we have that
$a|_{\\{x\\}\cup\tilde{z}_{1}}\cup
b|_{\\{y\\}\cup\tilde{z}_{2}}\notin\operatorname{sol}(R)$ or
$a|_{\\{y\\}\cup\tilde{z}_{2}}\cup
b|_{\\{x\\}\cup\tilde{z}_{1}}\notin\operatorname{sol}(R)$. Consider

$\displaystyle F_{n}:=\bigwedge_{i\in[n]}R(x_{i},y_{i},\vec{z}_{i})$

where the $\vec{z}_{i}$ are disjoint variable vectors. Let
$(\tilde{x},\tilde{y})$ be a variable partition for $F_{n}$ and $\mathcal{R}$
be a rectangle cover of $F_{n}$ such that each rectangle $\mathfrak{r}_{j}$ in
$\mathcal{R}$ respects the partition $(\tilde{x},\tilde{y})$. If for all
$i\in[n]$ we have that all $x_{i}\in\tilde{x}$ and $y_{i}\in\tilde{y}$ or
$x_{i}\in\tilde{y}$ and $y_{i}\in\tilde{x}$, then $\mathcal{R}$ has size at
least $2^{n}$.

######  Proof 6.13.

We use the so-called fooling set method from communication complexity, see
e.g. [KushilevitzN97, Section 1.3]. To this end, we will construct a set
$\mathcal{S}$ of satisfying assignments of $F_{n}$ such that every rectangle
of $\mathcal{R}$ can contain at most one assignment in $\mathcal{S}$.

So let $a_{i}$ be the assignment to $\\{x_{i},y_{i}\\}\cup\tilde{z}_{i}$ that
assigns the variables analogously to $a$, so $a_{i}(x_{i}):=a(x)$,
$a_{i}(y_{i}):=a(y)$, and $a_{i}(\vec{z}_{i}):=a(\vec{z})$. Define analogously
$b_{i}$. Then the set $\mathcal{S}$ consists of all assignments that we get by
choosing for every $i\in[n]$ an assignment $d_{i}$ as either $a_{i}$ or
$b_{i}$ and then combining the $d_{i}$ to one assignment to all variables of
$F_{n}$. Note that $\mathcal{S}$ contains $2^{n}$ assignments and that all of
them satisfy $F_{n}$, so all of them must be in a rectangle of $\mathcal{R}$.

We claim that none of the rectangles $\mathfrak{r}_{j}$ of $\mathcal{R}$ can
contain more than one element $d\in\mathcal{S}$. By way of contradiction,
assume this were not true. Then there is an $\mathfrak{r}_{j}$ that contains
two assignments $d,d^{\prime}\in\mathcal{S}$. Then there is an $i\in[n]$ such
that in the construction of $d$ we have chosen $a_{i}$ while in the
construction of $d^{\prime}$ we have chosen $b_{i}$. Let
$\tilde{x}_{j}:=\tilde{z}_{j}\cap\tilde{x}$ and
$\tilde{y}_{j}:=\tilde{z}_{j}\cap\tilde{y}$. Since
$d,d^{\prime}\in\operatorname{sol}(\mathfrak{r}_{j})$, we have that
$a_{i},b_{i}\in\operatorname{sol}(\pi_{\\{x_{i},y_{i}\\}\cup\tilde{x}_{j}\cup\tilde{y}_{j}}(\mathfrak{r}_{j}))$.
Moreover, by Observation 6.4,
$\pi_{\\{x_{i},y_{i}\\}\cup\tilde{x}_{j}\cup\tilde{y}_{j}}(\mathfrak{r}_{j})$
is a rectangle and so we have that $a_{i}|_{\\{x_{i}\\}\cup\tilde{x}_{j}}\cup
b_{i}|_{\\{y_{i}\\}\cup
y_{j}}\in\operatorname{sol}(\pi_{\\{x_{i},y_{i}\\}\cup\tilde{x}_{j}\cup\tilde{y}_{j}}(\mathfrak{r}_{j}))$
and $a_{i}|_{\\{y_{i}\\}\cup y_{j}}\cup b_{i}|_{\\{x_{i}\\}\cup
y_{j}}\in\operatorname{sol}(\pi_{\\{x_{i},y_{i}\\}\cup\tilde{x}_{j}\cup\tilde{y}_{j}}(\mathfrak{r}_{j}))$.
But $\mathfrak{r}$ consists only of solutions of $F_{n}$ and thus
$\operatorname{sol}(\pi_{\\{x_{i},y_{i}\\}\cup\tilde{x}_{j}\cup\tilde{y}_{j}}(\mathfrak{r}))\subseteq\operatorname{sol}(R(x_{i},y_{i},\vec{z}_{i}))$,
so $a_{i}|_{\\{x_{i}\\}\cup\tilde{x}_{j}}\cup b_{i}|_{\\{y_{i}\\}\cup
y_{j}},a_{i}|_{\\{y_{i}\\}\cup y_{j}}\cup b_{i}|_{\\{x_{i}\\}\cup
y_{j}}\in\operatorname{sol}(R(x_{i},y_{i},\vec{z}_{i}))$. It follows by
construction that there is a partition $(\tilde{x},\tilde{y})$ of $\tilde{z}$
such that $a|_{\\{x\\}\cup\tilde{x}}\cup b|_{\\{y\\}\cup\tilde{y}}$ and
$a|_{\\{y\\}\cup\tilde{y}}\cup b|_{\\{x\\}\cup\tilde{x}}$ are in
$\operatorname{sol}(R)$. This contradicts the assumption on $a$ and $b$ and
thus $\mathfrak{r}_{j}$ can only contain one assignment from $\mathcal{S}$.

Since $\mathcal{S}$ has size $2^{n}$ and all of assignments in $\mathcal{S}$
must be in one rectangle of $\mathcal{R}$, it follows that $\mathcal{R}$
consists of at least $2^{n}$ rectangles.

We now prove the lower bound of Proposition 6.11.

######  Proof 6.14 (Proof of Proposition 6.11).

Since $\Gamma$ is not strongly uniformly blockwise decomposable, let
$R(x,y,\vec{z})$ be a constraint in $\langle\Gamma\rangle$ that is not
uniformly blockwise decomposable in $x$ and $y$. If $R(x,y,\vec{z})$ is such
that $M^{R}_{x,y}$ is not a proper block matrix, then the lemma follows
directly from Lemma 6.3, so we assume in the remainder that $M^{R}_{x,y}$ is a
proper block matrix. We denote for every block $D_{1}\times D_{2}$ of
$R(x,y,\vec{z})$ by $R^{D_{1}\times D_{2}}(x,y,\vec{z})$ the sub-constraint of
$R(x,y,\vec{z})$ we get by restricting $x$ to $D_{1}$ and $y$ to $D_{2}$.
Since $R(x,y,\vec{z})$ is not uniformly blockwise decomposable, for every
partition $(\tilde{z}_{1},\tilde{z}_{2})$ of $\tilde{z}$ there is a block
$D_{1}\times D_{2}$ such that $R^{D_{1}\times
D_{2}}(x,y,\vec{z})\neq\pi_{\\{x\\}\cup\tilde{z}_{1}}R^{D_{1}\times
D_{2}}(x,y,\vec{z})\times\pi_{\\{y\\}\cup\tilde{z}_{2}}R^{D_{1}\times
D_{2}}(x,y,\vec{z})$.

Given a bipartite graph $G=(A,B,E)$, we construct the same formula $F(G)$ as
in the proof of Lemma 6.3. Consider again the graphs $G_{n}$ of the family
from Lemma 6.4 and let $F_{n}:=F(G_{n})$. Fix $n$ in the remainder of the
proof. Let $O$ be a structured DNNF representing $F_{n}$ of size $s$. Then
there is by Proposition 6 a balanced partition $(X_{1},X_{2})$ of $X_{A}\cup
X_{B}$ such that there is a rectangle cover of $F_{G}$ of size at most $s$ and
such that all rectangles respect the partition $(X_{1},X_{2})$. Let
$E^{\prime}$ be the set of edges $uv\in E$ such that $x_{u}$ and $x_{v}$ are
in different parts of the partition $(X_{1},X_{2})$. By the properties of
$G_{n}$, there is an induced matching $\mathcal{M}$ of size $\Omega(|A|+|B|)$
consisting of edges in $E^{\prime}$.

For every edge $e=uv\in\mathcal{M}$ let $\tilde{z}_{e,1}:=\tilde{z}_{e}\cap
X_{1}$ and $\tilde{z}_{e,2}:=\tilde{z}_{2}\cap X_{2}$. Assume that $x_{u}\in
X_{1}$ and $y_{v}\in X_{2}$ (the other case is treated analogously). Then we
know that there is a block $D_{1}\times D_{2}$ of $M^{R}_{x,y}$ such that

$\displaystyle R^{D_{1}\times
D_{2}}(x_{u},y_{v},\vec{z}_{e})\neq\pi_{\\{x_{u}\\}\cup\vec{z}_{e,1}}R^{D_{1}\times
D_{2}}(x_{u},y_{v},\vec{z}_{e})\times\pi_{\\{y_{v}\\}\cup\vec{z}_{e,2}}R^{D_{1}\times
D_{2}}(x_{u},y_{v},\vec{z}_{e}).$ (14)

Since there are only at most $|D|$ blocks in $M^{R}_{x,y}$, there is a block
$D_{1}\times D_{2}$ such that for at least
$\Omega\left(\frac{|A|+|B|}{|D|}\right)=\Omega({|A|+|B|})$ edges Equation (14)
is true. Call this set of edges $E^{*}$.

Let $X^{*}:=\\{x_{u}\mid u\text{ is an endpoint of an edge }e\in E^{*}\\}$. We
construct a structured DNNF $O^{\prime}$ from $O$ by existentially quantifying
all variables not in a constraint $R(x_{u},y_{v},\vec{z}_{e})$ for $e=uv\in
E^{*}$ and for all $x_{u}\in X^{*}$ restricting the domain to $D_{1}$ $u\in A$
and to $D_{2}$ if $u\in B$. Note that every assignment to $X^{*}$ that assigns
every variable $x_{v}$ with $v\in A$ to a value in $D_{1}$ and every $x_{v}$
with $v\in B$ to a value in $D_{2}$ can be extended to a satisfying assignment
of $F_{n}$, because $D_{1}\times D_{2}$ is a block. Thus, $O^{\prime}$ is a
representation of

$\displaystyle F^{*}:=\bigwedge_{e=uv\in E^{*}}R^{D_{1}\times
D_{2}}(x_{u},y_{v},\vec{z}_{e}).$

We now use the following simple observation.

######  Claim 3.

Let $R^{\prime}(\vec{x},\vec{y})$ be a constraint such that
$R^{\prime}(\vec{x},\vec{y})\neq\pi_{\vec{x}}(R^{\prime}(\vec{x},\vec{y}))\times\pi_{\vec{y}}(R^{\prime}(\vec{x},\vec{y}))$.
Then there are assignments
$a,b\in\operatorname{sol}(R^{\prime}(\vec{x},\vec{y}))$ such that
$a|_{\vec{x}}\cup
b|_{\vec{y}}\notin\operatorname{sol}(R^{\prime}(\vec{x},\vec{y}))$ or
$a|_{\vec{x}}\cup
b|_{\vec{y}}\notin\operatorname{sol}(R^{\prime}(\vec{x},\vec{y}))$.

Since
$R(\vec{x},\vec{y})\neq\pi_{\vec{x}}(R(\vec{x},\vec{y}))\times\pi_{\vec{y}}(R(\vec{x},\vec{y}))$
and thus
$R(\vec{x},\vec{y})\subsetneq\pi_{\vec{x}}(R(\vec{x},\vec{y}))\times\pi_{\vec{y}}(R(\vec{x},\vec{y}))$,
we have that there is
$a_{x}\in\operatorname{sol}(\pi_{\vec{x}}(R(\vec{x},\vec{y})))$ and
$b_{y}\in\operatorname{sol}(\pi_{\vec{y}}(R(\vec{x},\vec{y})))$ such that
$a|_{\vec{x}}\cup b|_{\vec{y}}\notin\operatorname{sol}(R(\vec{x},\vec{y}))$.
Simply extending $a_{x}$ and $b_{y}$ to an assignment in $R(\vec{x},\vec{y})$
yields the claim.

Since Claim 3 applies to all constraints in $F^{*}$, we are now in a situation
where we can use Lemma 6.12 which shows that any rectangle cover respecting
the partition $(X_{1},X_{2})$ for $F^{*}$ has size
$2^{|E^{*}|}=2^{\Omega(|A|+|B|)}$. With Lemma 6, we know that
$\|O^{\prime}\|=2^{\Omega(|A|+|B|)}$ and since the construction of
$O^{\prime}$ from $O$ does not increase the size of the DNNF, we get
$s=\|O\|=2^{\Omega(|A|+|B|)}=2^{\Omega(\|F^{*}\|)}=2^{\Omega(\|F\|)}$.

##  7 The Boolean Case

In this section, we will specialize our dichotomy results for the Boolean
domain $\\{0,1\\}$. A relation $R$ over $\\{0,1\\}$ is called _bijunctive
affine_ if it can be written as a conjunction of the relations $x=y$ and
$x\neq y$ and unary relations, so $R\subseteq E$ with
$E=\left<\\{=,\neq,U_{0},U_{1}\\}\right>$ where $U_{0}=\\{0\\}$ and
$U_{1}=\\{1\\}$}. A set of relations $\Gamma$ is called bijunctive affine if
all $R\in\Gamma$ are bijunctive affine. We will show the following dichotomy
for the Boolean case:

Let $\Gamma$ be a constraint language. If all relations in $\Gamma$ are
bijunctive affine, then there is an polynomial time algorithm that, given a
$\Gamma$-formula $F$, constructs an $OBDD$ for $F$. If not, then there are
formulas $F_{n}$ and $\varepsilon>0$ such that an $DNNF$ for $F_{n}$ needs to
have a size of at least $2^{\varepsilon\left\|F_{n}\right\|}$. We prove
Theorem 7 in the appendix. Let us remark here that, in contrast to general
domains $D$, there is no advantage of FDD over ODD in the Boolean case: either
a constraint language allows for efficient representation by ODD or it is hard
even for DNNF. So in a sense, the situation over the Boolean domain is easier.
Also note that the tractable cases over the Boolean domain are very
restricted, allowing only equalities and disequalities.

######  Proof 7.1.

With Theorem 3.7 and Theorem 3.8, we only need to show the following:

  1. 1.

Every $\Gamma\subseteq\langle E\rangle$ is strongly uniformly blockwise
decomposable.

  2. 2.

If $\Gamma$ is strongly blockwise decomposable, then $\Gamma\subseteq\langle
E\rangle$.

We show that $E$ is strongly uniformly blockwise decomposable – which implies
that every $\Gamma\subseteq\langle E\rangle$ is also strongly uniformly
blockwise decomposable. Let $R\in\langle E\rangle$. Then $R$ can be
constructed by conjunctions of constraints in the relations of $E$ and
projections. Let $R^{\prime}$ be the relation we get by the same conjunctions
as for $R$ but not doing any of the projections. By Lemma 4, it suffices to
show that $R^{\prime}$ is uniformly blockwise decomposable. To this end,
consider the graph $G_{R^{\prime}}$ with $V(G_{R^{\prime}})=var(R^{\prime})$,
two vertices $x$ and $y$ are connected with a blue edge if the representation
of $R^{\prime}$ contains $x=y$ and connected with a red edge if $R^{\prime}$
contains $x\neq y$. A vertex $x$ is blue if $R^{\prime}$ contains $U_{1}(x)$
and red if $R$ contains $U_{0}(x)$.

######  Example 7.2.

If $R^{\prime}$ is represented by

$R^{\prime}(a,b,c,d,e,f)=(a=b)\wedge(c=d)\wedge(b\neq c)\wedge(b\neq
d)\wedge(e\neq f)\wedge(b=1)\wedge(d=0),$

then $G_{R}^{\prime}$ is the graph in Figure 1.

$e$$f$$d$$a$$b$$c$ Figure 1: The graph $G_{R^{\prime}}$ from example 7.2.

We show that $M_{x,y}^{R^{\prime}}$ is a proper block matrix and each block is
decomposable using the same variable partition. If $x$ and $y$ are in
different connected components of $G_{R^{\prime}}$, $R^{\prime}$ is
decomposable such that $x$ and $y$ appear in different factors, so
$M_{x,y}^{R}$ has only one block which is decomposable. If $R^{\prime}$ has no
satisfying assignments, there is nothing to show. It remains the case where
$R$ has satisfying assignments and $x$ and $y$ are in the same connected
component.

So let $R^{\prime}(\vec{x})$ have at least one model and let $G_{R^{\prime}}$
have only one connected component. Note that setting one variable in
$\tilde{x}$ to $0$ or $1$ determines the value of all other variables in
$\tilde{x}$. This implies that if a vertex in $G_{R^{\prime}}$ is colored,
then $M_{x,y}^{R}$ has three empty entries and one entry with exactly one
element. If no vertex in $G_{R^{\prime}}$ is colored, then
$\pi_{x,y}(R^{\prime}(\vec{x}))$ is either $x=y$ (if every path from $x$ to
$y$ has an even number of red edges) or $x\neq y$ (if every path from $x$ to
$y$ has an odd number of edges). So $M_{x,y}^{R^{\prime}}$ has exactly two
non-empty entries with one element each, so $R$ is decomposable in $x$ and
$y$. This completes the proof of Item 1.

Let now $\Gamma$ be strongly blockwise decomposable and
$R\in\left<\Gamma\right>$ be decomposed into indecomposable factors

$R(\vec{x})=R_{1}(\vec{x}_{1})\times\cdots\times R_{k}(\vec{x}_{k})$

We have to show that $R_{i}\in\langle E\rangle$ for all $i$ which implies that
$R\in\langle E\rangle$). Since $R_{i}(\vec{x}_{i})$ is indecomposable,
$M_{x,y}^{R_{i}}$ has to have at least two blocks for every $x,y\in
var(R_{i})$. Since $R$ is Boolean, only two cases remain:
$\pi_{x,y}R_{i}(\vec{x}_{i})$ is either equality or disequality on $x$ and
$y$. In every case, the value of $y$ determines the value of $x$ and vice
versa. Since $x$ and $y$ are arbitrary, each variable in $\tilde{x}_{i}$
determines the value of every other variable in $\tilde{x}_{i}x`$. This
implies that non-empty entries of $M_{x,y}^{R_{i}}$ have exactly one element.
It follows that $R_{i}(\vec{x}_{i})$ has exactly two satisfying assignments
and moreover, no variable can take the same value in these two assignments
since otherwise $R_{i}(\vec{x}_{i})$ would be decomposable. It follows that
after fixing a value for a variable $x$, the values of all other variables $y$
are determined by the constraint $x\neq y$ or $x=y$, so $R_{i}(\vec{x}_{i})$
is a conjunction of constraints with relations in $E$ which completes the
proof of Item 2 and thus the theorem.

##  8 Conclusion

We have seen that there is a dichotomy for compiling systems of constraints
into DNNF based on the constraint languages. It turns out that the constraint
languages that allow efficient compilation are rather restrictive, in the
Boolean setting they consist essentially only of equality and disequality.
From a practical perspective, our results are thus largely negative since
interesting settings will most likely lie outside the tractable cases we have
identified.

One question that we leave for future work is that of decidability. Given a
constraint language, can one decide if it is (uniformly) blockwise
decomposable? We remark that for the similar property in counting complexity
from [DyerR13], it is known that the dichotomy criterion is decidable. But we
do currently not yet understand if a similar result is possible in our
setting.

## References

  * [1] Noga Alon, Mrinal Kumar, and Ben Lee Volk.  Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits.  Comb., 40(2):149–178, 2020.
  * [2] Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel.  A circuit-based approach to efficient enumeration.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 111:1–111:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [3] Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart.  Connecting knowledge compilation classes and width parameters.  Theory Comput. Syst., 64(5):861–914, 2020.
  * [4] Jérôme Amilhastre, Hélène Fargier, Alexandre Niveau, and Cédric Pralet.  Compiling csps: A complexity map of (non-deterministic) multivalued decision diagrams.  Int. J. Artif. Intell. Tools, 23(4), 2014.
  * [5] Christoph Berkholz and Harry Vinall-Smeeth.  A dichotomy for succinct representations of homomorphisms.  In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 113:1–113:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [6] Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky.  Expander cnfs have exponential DNNF size.  CoRR, abs/1411.1995, 2014.
  * [7] Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky.  Knowledge compilation meets communication complexity.  In Subbarao Kambhampati, editor, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 1008–1014. IJCAI/AAAI Press, 2016.
  * [8] Randal E. Bryant.  Graph-based algorithms for boolean function manipulation.  IEEE Trans. Computers, 35(8):677–691, 1986.
  * [9] Andrei A. Bulatov.  The complexity of the counting constraint satisfaction problem.  In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 646–661. Springer, 2008.
  * [10] Andrei A. Bulatov.  A dichotomy theorem for nonuniform csps.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319–330. IEEE Computer Society, 2017.
  * [11] Florent Capelli.  Understanding the complexity of #sat using knowledge compilation.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–10. IEEE Computer Society, 2017.
  * [12] Florent Capelli and Stefan Mengel.  Tractable QBF by Knowledge Compilation.  In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [13] Arthur Choi and Adnan Darwiche.  Dynamic minimization of sentential decision diagrams.  In Marie desJardins and Michael L. Littman, editors, Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA, pages 187–194. AAAI Press, 2013\.
  * [14] Nadia Creignou.  A dichotomy theorem for maximum generalized satisfiability problems.  J. Comput. Syst. Sci., 51(3):511–522, 1995.
  * [15] Nadia Creignou and Miki Hermann.  Complexity of generalized satisfiability counting problems.  Inf. Comput., 125(1):1–12, 1996.
  * [16] Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.  Complexity classifications of boolean constraint satisfaction problems.  SIAM, 2001.
  * [17] Nadia Creignou, Frédéric Olive, and Johannes Schmidt.  Enumerating all solutions of a boolean CSP by non-decreasing weight.  In Karem A. Sakallah and Laurent Simon, editors, Theory and Applications of Satisfiability Testing - SAT 2011 - 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings, volume 6695 of Lecture Notes in Computer Science, pages 120–133. Springer, 2011.
  * [18] Víctor Dalmau and Peter Jonsson.  The complexity of counting homomorphisms seen from the other side.  Theor. Comput. Sci., 329(1-3):315–323, 2004.
  * [19] Adnan Darwiche.  Decomposable negation normal form.  J. ACM, 48(4):608–647, 2001.
  * [20] Adnan Darwiche.  New advances in compiling CNF into decomposable negation normal form.  In Ramón López de Mántaras and Lorenza Saitta, editors, Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI’2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004, pages 328–332. IOS Press, 2004.
  * [21] Adnan Darwiche and Pierre Marquis.  A knowledge compilation map.  J. Artif. Intell. Res., 17:229–264, 2002.
  * [22] Guy Van den Broeck and Dan Suciu.  Query processing on probabilistic data: A survey.  Found. Trends Databases, 7(3-4):197–341, 2017.
  * [23] Martin E. Dyer and David Richerby.  An effective dichotomy for the counting constraint satisfaction problem.  SIAM J. Comput., 42(3):1245–1274, 2013.
  * [24] Hélène Fargier and Pierre Marquis.  On the use of partially ordered decision graphs in knowledge compilation and quantified boolean formulae.  In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pages 42–47. AAAI Press, 2006.
  * [25] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM, 54(1), mar 2007.
  * [26] Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson.  The approximability of constraint satisfaction problems.  SIAM J. Comput., 30(6):1863–1920, 2000.
  * [27] Frédéric Koriche, Jean-Marie Lagniez, Pierre Marquis, and Samuel Thomas.  Compiling constraint networks into multivalued decomposable decision graphs.  In Qiang Yang and Michael Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 332–338. AAAI Press, 2015.
  * [28] Eyal Kushilevitz and Noam Nisan.  Communication complexity.  Cambridge University Press, 1997.
  * [29] Jean-Marie Lagniez and Pierre Marquis.  An improved decision-dnnf compiler.  In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 667–673. ijcai.org, 2017.
  * [30] Robert Mateescu and Rina Dechter.  Compiling constraint networks into AND/OR multi-valued decision diagrams (aomdds).  In Frédéric Benhamou, editor, Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings, volume 4204 of Lecture Notes in Computer Science, pages 329–343. Springer, 2006.
  * [31] Robert Mateescu, Rina Dechter, and Radu Marinescu.  AND/OR multi-valued decision diagrams (aomdds) for graphical models.  J. Artif. Intell. Res., 33:465–519, 2008.
  * [32] Christian J. Muise, Sheila A. McIlraith, J. Christopher Beck, and Eric I. Hsu.  Dsharp: Fast d-dnnf compilation with sharpsat.  In Leila Kosseim and Diana Inkpen, editors, Advances in Artificial Intelligence - 25th Canadian Conference on Artificial Intelligence, Canadian AI 2012, Toronto, ON, Canada, May 28-30, 2012. Proceedings, volume 7310 of Lecture Notes in Computer Science, pages 356–361. Springer, 2012.
  * [33] Dan Olteanu.  Factorized databases: A knowledge compilation perspective.  In Adnan Darwiche, editor, Beyond NP, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA, February 12, 2016, volume WS-16-05 of AAAI Technical Report. AAAI Press, 2016.
  * [34] Dan Olteanu and Jakub Závodný.  Size bounds for factorised representations of query results.  ACM Trans. Database Syst., 40(1):2:1–2:44, 2015.
  * [35] Umut Oztok and Adnan Darwiche.  A top-down compiler for sentential decision diagrams.  In Qiang Yang and Michael J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 3141–3148. AAAI Press, 2015.
  * [36] Knot Pipatsrisawat and Adnan Darwiche.  New compilation languages based on structured decomposability.  In Dieter Fox and Carla P. Gomes, editors, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008, pages 517–522. AAAI Press, 2008\.
  * [37] Ran Raz, Amir Shpilka, and Amir Yehudayoff.  A lower bound for the size of syntactically multilinear arithmetic circuits.  SIAM J. Comput., 38(4):1624–1647, 2008.
  * [38] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216–226. ACM, 1978.
  * [39] Ingo Wegener.  Branching Programs and Binary Decision Diagrams.  SIAM, 2000.
  * [40] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331–342. IEEE Computer Society, 2017.