LTCI, Télécom Paris, Institut polytechnique de Paris, France and
https://a3nm.net/antoine.amarilli@telecom-
paris.frhttps://orcid.org/0000-0002-7977-4441Amarilli was partially supported
by the ANR project EQUUS ANR-19-CE48-0019, by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) – 431183758, and by
the ANR project ANR-18-CE23-0003-02 (“CQFD”). This work was done in part while
the author was visiting the Simons Institute for the Theory of Computing.
National University of Singapore,
Singaporetvanbr@nus.edu.sghttps://orcid.org/0009-0004-0538-3044University of
Toronto, Canadameel@cs.toronto.eduhttps://orcid.org/0000-0001-9423-5270
Antoine Amarilli, Timothy van Bremen and Kuldeep S. Meel [500]Theory of
computation Database query processing and optimization (theory)

# Conjunctive Queries on Probabilistic Graphs:
The Limits of Approximability

Antoine Amarilli  Timothy van Bremen  Kuldeep S. Meel

###### Abstract

Query evaluation over probabilistic databases is a notoriously intractable
problem—not only in combined complexity, but for many natural queries in data
complexity as well [7, 14]. This motivates the study of probabilistic query
evaluation through the lens of approximation algorithms, and particularly of
combined FPRASes, whose runtime is polynomial in both the query and instance
size. In this paper, we focus on tuple-independent probabilistic databases
over binary signatures, which can be equivalently viewed as probabilistic
graphs. We study in which cases we can devise combined FPRASes for
probabilistic query evaluation in this setting.

We settle the complexity of this problem for a variety of query and instance
classes, by proving both approximability and (conditional) inapproximability
results. This allows us to deduce many corollaries of possible independent
interest. For example, we show how the results of [8] on counting fixed-length
strings accepted by an NFA imply the existence of an FPRAS for the two-
terminal network reliability problem on directed acyclic graphs: this was an
open problem until now [36]. We also show that one cannot extend a recent
result [33] that gives a combined FPRAS for self-join-free conjunctive queries
of bounded hypertree width on probabilistic databases: neither the bounded-
hypertree-width condition nor the self-join-freeness hypothesis can be
relaxed. Finally, we complement all our inapproximability results with
unconditional lower bounds, showing that DNNF provenance circuits must have at
least moderately exponential size in combined complexity.

###### keywords:

Probabilistic query evaluation; tuple-independent databases; approximation

###### category:

##  1 Introduction

Tuple-independent probabilistic databases (TID) are a simple and principled
formalism to model uncertainty and noise in relational data [13, 31]. In the
TID model, each tuple of a relational database is annotated with an
independent probability of existence; all tuples are assumed to be
independent. In the probabilistic query evaluation (PQE) problem, given a
Boolean query $Q$ and a TID instance $I$, we must compute the probability that
$Q$ holds in a subinstance sampled from $I$ according to the resulting
distribution. The PQE problem has been studied in database theory both in
terms of _combined complexity_ , where the query and instance are part of the
input, and in _data complexity_ , where the query is fixed and only the
instance is given as input [34]. Unfortunately, many of the results so far
[31] show that the PQE problem is highly intractable, even in data complexity
for many natural queries (e.g., a path query of length three), and hence also
in combined complexity.

Faced with this intractability, a natural approach is to study _approximate
PQE_ : we relax the requirement of computing the exact probability that the
query holds, and settle for an approximate answer. This approach has been
studied in data complexity [31]: for any fixed union of conjunctive queries
(UCQ), we can always tractably approximate the answer to PQE, additively
(simply by Monte Carlo sampling), or multiplicatively (using the Karp-Luby
approximation algorithm on a disjunctive-normal-form representation of the
query provenance). However, these approaches are not tractable in combined
complexity, and moreover the latter approach exhibits a “slicewise polynomial”
runtime of the form $O(|I|^{|Q|})$—rather than, say,
$O(2^{|Q|}\mathsf{poly}(|I|))$—which seriously limits its practical utility.
Thus, our goal is to obtain a combined FPRAS for PQE: by this we mean a fully
polynomial-time randomized approximation scheme, giving a multiplicative
approximation of the probability, whose runtime is polynomial in the query and
TID (and in the desired precision). This approach has been recently proposed
by van Bremen and Meel [33], who show a combined FPRAS for CQs when assuming
that the query is self-join-free and has bounded hypertree width; their work
leaves open the question of which other cases admit combined FPRASes.

### Main Results.

In this paper, following the work of Amarilli, Monet and Senellart [7] for
exact PQE, we investigate the combined complexity of approximate PQE in the
setting of probabilistic graphs. In other words, we study probabilistic graph
homomorphism, which is the equivalent analogue of CQ evaluation: given a
(deterministic) query graph $G$, and given a instance graph $H$ with edges
annotated with independent probabilities (like a TID), we wish to approximate
the probability that a randomly selected subgraph $H^{\prime}\subseteq H$
admits a homomorphism from $G$. This setting is incomparable to that of [33],
because it allows for self-joins and for queries of unbounded width, but
assumes that relations are binary. For a variety of graph classes from [7], we
show either (i) the existence of a combined FPRAS, or (ii) the non-existence
of such an FPRAS, subject to standard complexity-theoretic assumptions. We
summarize our results in Table 1, respectively for graphs that are _labelled_
(i.e., the signature features several binary relations), or _unlabelled_
(i.e., only one binary relation).

######  Result  (Sections 3 and 4).

The results in Table 1 hold.

In summary, our results mostly show that, on connected probabilistic graphs,
the general intractability of combined PQE carries over in many settings to
the approximate PQE problem. There is, however, an important exception: the
PQE problem for one-way path queries on _directed acyclic graphs_ (DAGs)
admits a combined FPRAS, implying the same for downwards trees on DAGs in the
unlabelled setting. We discuss more in detail below how this result is proved
and some of its consequences. Another case is left open: in the unlabelled
setting, we do not settle the approximability of combined PQE for one-way path
queries (or equivalently downwards trees queries) on connected graphs. For all
other cases, either exact combined PQE was already shown to be tractable in
the exact setting [7], or we strengthen the $\\#\mathsf{P}$-hardness of exact
PQE from [7] by showing that combined FPRASes conditionally do not exist. Note
that our intractability results are always shown in _combined complexity_ —in
data complexity, PQE is always multiplicatively approximable via the Karp-Luby
algorithm [31].

As an important consequence, our techniques yield connections between
approximate PQE and intensional approaches to the PQE problem. Recall that the
intensional approach was introduced by Jha and Suciu [20] in the setting of
exact evaluation, and when measuring data complexity. They show that many
tractable queries for PQE also admit tractable provenance representations.
More precisely, for these queries $Q$, there is a polynomial-time algorithm
that takes as input any database instance and computes a representation of the
Boolean provenance of $Q$ in a form which admits tractable model counting
(e.g., OBDD, d-DNNF, etc.). This intensional approach contrasts with
extensional approaches (like [14]) which exploit the structure of the query
directly: comparing both approaches is still open [26].

In line with this intensional approach, we complement our conditional hardness
results on approximate PQE with _unconditional_ lower bounds on the combined
size of tractable representations of query provenance. Namely, we show a
moderately exponential lower bound on DNNF provenance representations for all
our non-approximable query-instance class pairs:

######  Result  (Section 5, informal).

Let $\langle\mathcal{G},\mathcal{H}\rangle$ be a conditionally non-
approximable query-instance class pair studied in this paper. For any
$\epsilon>0$, there is an infinite family $G_{1},G_{2},\ldots$ of
$\mathcal{G}$ queries and an infinite family $H_{1},H_{2},\ldots$ of
$\mathcal{H}$ instances such that, for any $i>0$, any DNNF circuit
representing the provenance $\mathsf{Prov}^{G_{i}}_{H_{i}}$ has size at least
$2^{\Omega\left(\left(|G_{i}|+|H_{i}|\right)^{1-\epsilon}\right)}$.

The class of DNNF circuits is arguably the most succinct circuit class in
knowledge compilation that still has desirable properties [15, 16]. Such
circuits subsume in particular the class of _structured DNNFs_ , for which
tractable approximation algorithms were recently proposed [9]. Thus, these
bounds help to better understand the limitations of intensional approaches.

### Consequences.

Our results and techniques have several interesting consequences of potential
independent interest. First, they imply that we cannot relax the hypotheses of
the result of van Bremen and Meel mentioned earlier [33]. They show the
following result on combined FPRASes for PQE in the more general context of
probabilistic databases:

######  Theorem 1.1 (Theorem 1 of [33]).

Let $Q$ be a self-join-free conjunctive query of bounded hypertree width, and
$H$ a tuple-independent database instance. Then there exists a combined FPRAS
for computing the probability of $Q$ on $H$, i.e., an FPRAS whose runtime is
$\mathsf{poly}(|Q|,|H|,\epsilon^{-1})$, where $\epsilon$ is the multiplicative
error.

It was left open in [33] whether intractability held without these assumptions
on the query. Hardness is immediate if we do not bound the width of queries
and allow arbitrary self-join-free CQs, as combined query evaluation is then
$\mathsf{NP}$-hard already in the non-probabilistic setting. However, it is
less clear whether the self-join-freeness condition can be lifted. Our results
give a negative answer, already in a severely restricted setting:

######  Result 1.2 (Corollaries 6.1 and 6.2).

Assuming $\mathsf{RP}\neq\mathsf{NP}$, neither the bounded hypertree width nor
self-join-free condition in Theorem 1.1 can be relaxed: even on a fixed
signature consisting of a single binary relation, there is no FPRAS to
approximate the probability of an input treewidth-1 CQ on an input treewidth-1
TID instance.

A second consequence implied by our techniques concerns the two-terminal
network reliability problem on directed acyclic graphs (DAGs). Roughly
speaking, given a directed graph $G=(V,E)$ with independent edge reliability
probabilities $\pi:E\rightarrow[0,1]$, and two distinguished vertices $s,t\in
V$, the two-terminal network reliability problem asks for the probability that
there is a path from $s$ to $t$. The problem is known to be
$\\#\mathsf{P}$-hard even on DAGs [28, Table 2]. The existence of an FPRAS for
the two-terminal network reliability problem is a long-standing open question
[21], and the case of DAGs was explicitly left open by Zenklusen and Laumanns
[36]. Our results allow us to answer in the affirmative:

######  Result 1.3 (Theorem 6.3).

There exists an FPRAS for the two-terminal network reliability problem over
DAGs.

This result and our approximability results follow from the observation that
path queries on directed acyclic graphs admit a compact representation of
their Boolean provenance as non-deterministic ordered binary decision diagrams
(nOBDDs). We are then able to use a recent result by Arenas et al. [8,
Corollary 4.5] giving an FPRAS for counting the satisfying assignments of an
nOBDD, adapted to the weighted setting.

### Paper Structure.

In Section 2, we review some of the technical background. We then present our
main results on approximability, divided into the labelled and unlabelled
case, in Sections 3 and 4 respectively. Next, in Section 5, we show lower
bounds on DNNF provenance circuit sizes. In Section 6, we show some
consequences for previous work [33], as well as for the two-terminal network
reliability problem. We conclude in Section 7.

##  2 Preliminaries

We provide some technical background below, much of which closes follows that
in [4] and [7].

### Graphs and Graph Homomorphisms.

Let $\sigma$ be an non-empty finite set of labels. When $|\sigma|>1$, we say
that we are in the labelled setting, and when $|\sigma|=1$, the unlabelled
setting. In this paper, we study only directed graphs with edge labels from
$\sigma$. A graph $G$ over $\sigma$ is a tuple $(V,E,\lambda)$ with finite
non-empty vertex set $V$, edge set $E\subseteq V^{2}$, and $\lambda\colon
E\to\sigma$ a labelling function mapping each edge to a single label (we may
omit $\lambda$ in the unlabelled setting). The _size_ $|G|$ of $G$ is its
number of edges. We write $x\xrightarrow{R}y$ for an edge $e=(x,y)\in E$ with
label $\lambda(e)=R$, and $x\xrightarrow{}y$ for $(x,y)\in E$ (no matter the
edge label). A graph $H=(V^{\prime},E^{\prime},\lambda^{\prime})$ is a
subgraph of $G$, written $H\subseteq G$, if $V=V^{\prime}$,
$E^{\prime}\subseteq E$, and $\lambda^{\prime}$ is the restriction of
$\lambda$ to $E$.

A graph homomorphism $h$ from a graph $G=(V_{G},E_{G},\lambda_{G})$ to a graph
$H=(V_{H},E_{H},\lambda_{H})$ is a function $h:V_{G}\rightarrow V_{H}$ such
that, for all $(u,v)\in E_{G}$, we have $(h(u),h(v))\in E_{H}$ and
$\lambda_{H}((h(u),h(v))=\lambda_{G}((u,v))$. We write $G\rightsquigarrow H$
to say that such a homomorphism exists.

### Probabilistic Graphs and Probabilistic Graph Homomorphism.

A probabilistic graph is a pair $(H,\pi)$, where $H$ is a graph with edge
labels from $\sigma$, and $\pi:E\to[0,1]$ is a probability labelling on the
edges. Note that edges $e$ in $H$ are annotated both by their probability
value $\pi(e)$ and their $\sigma$-label $\lambda(e)$. Intuitively, $\pi$ gives
us a succinct specification of a probability distribution over the $2^{|H|}$
possible subgraphs of $H$, by independently including each edge $e$ with
probability $\pi(e)$. Formally, the distribution induced by $\pi$ on the
subgraphs $H^{\prime}\subseteq H$ is defined by
$\Pr_{\pi}(H^{\prime})=\prod_{e\in E^{\prime}}\pi(e)\prod_{e\in E\setminus
E^{\prime}}(1-\pi(e))$.

In this paper, we study the probabilistic graph homomorphism problem
$\mathsf{PHom}$ for a fixed set of labels $\sigma$: given a graph $G$ called
the _query graph_ and a probabilistic graph $(H,\pi)$ called the _instance
graph_ , both using labels from $\sigma$, we must compute the probability
$\Pr_{\pi}(G\rightsquigarrow H)$ that a subgraph of $H$, sampled according to
the distribution induced by $\pi$, admits a homomorphism from $G$. That is, we
must compute $\Pr_{\pi}(G\rightsquigarrow
H):=\sum_{\begin{subarray}{c}H^{\prime}\subseteq H\text{\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ }G\rightsquigarrow
H^{\prime}\end{subarray}}\Pr_{\pi}(H^{\prime})$.

We study $\mathsf{PHom}$ in _combined complexity_ , i.e., when both the query
graph $G$ and instance graph $(H,\pi)$ are given as input. Further, we study
$\mathsf{PHom}$ when we restrict $G$ and $H$ to be taken from specific _graph
classes_ , i.e., infinite families of (non-probabilistic) graphs, denoted
respectively $\mathcal{G}$ and $\mathcal{H}$. (Note that $\mathcal{H}$ does
not restrict the probability labelling $\pi$.) To distinguish the labelled and
unlabelled setting, we denote by $\mathsf{PHom_{L}}(\mathcal{G},\mathcal{H})$
the problem of computing $\Pr_{\pi}(G\rightsquigarrow H)$ for
$G\in\mathcal{G}$ and $(H,\pi)$ with $H\in\mathcal{H}$ when the fixed set of
allowed labels in $\mathcal{G}$ and $\mathcal{H}$ has cardinality
$|\sigma|>1$, and likewise write $\mathsf{PHom_{\centernot
L}}(\mathcal{G},\mathcal{H})$ when $\mathcal{G}$ and $\mathcal{H}$ are classes
of unlabelled graphs. We focus on _approximation algorithms_ : fixing classes
$\mathcal{G}$ and $\mathcal{H}$, a _fully polynomial-time randomized
approximation scheme_ (FPRAS) for $\mathsf{PHom_{L}}(\mathcal{G},\mathcal{H})$
(in the labelled setting) or $\mathsf{PHom_{\centernot
L}}(\mathcal{G},\mathcal{H})$ (in the unlabelled setting) is a randomized
algorithm that runs in time $\mathsf{poly}(|G|,|H|,\epsilon^{-1})$ on inputs
$G\in\mathcal{G}$, $(H,\pi)$ for $H\in\mathcal{H}$, and $\epsilon>0$. The
algorithm must return, with probability at least $3/4$, a _multiplicative
approximation_ of the probability $\Pr_{\pi}(G\rightsquigarrow H)$, i.e., a
value between $(1-\epsilon)\Pr_{\pi}(G\rightsquigarrow H)$ and
$(1+\epsilon)\Pr_{\pi}(G\rightsquigarrow H)$.

### Graph Classes.

We study $\mathsf{PHom}$ on the following graph classes, which are defined on
a graph $G$ with edge labels from $\sigma$, and are either labelled or
unlabelled depending on $\sigma$:

  * •

$G$ is a one-way path ($\mathsf{1WP}$) if it is of the form
$a_{1}\xrightarrow{R_{1}}\dots\xrightarrow{R_{m-1}}a_{m}$ for some $m$, with
all $a_{1},\dots,a_{m}$ being pairwise distinct, and with $R_{i}\in\sigma$ for
$1\leq i<m$.

  * •

$G$ is a two-way path ($\mathsf{2WP}$) if it is of the form $a_{1}\ -\ \dots\
-\ a_{m}$ for some $m$, with pairwise distinct $a_{1},\dots,a_{m}$, and each
$-$ being $\xrightarrow{R_{i}}$ or $\xleftarrow{R_{i}}$ (but not both) for
some label $R_{i}\in\sigma$.

  * •

$G$ is a downwards tree ($\mathsf{DWT}$) if it is a rooted unranked tree (each
node can have an arbitrary number of children), with all edges pointing from
parent to child in the tree.

  * •

$G$ is a polytree ($\mathsf{PT}$) if its underlying undirected graph is a
rooted unranked tree, without restrictions on the edge directions.

  * •

$G$ is a DAG ($\mathsf{DAG}$) if it is connected (i.e., the underlying
undirected graph is connected) and (directed) acyclic.

  * •

$G$ is connected ($\mathsf{Conn}$) if it is an arbitrary connected graph.

These refine the classes of connected queries considered in [7], by adding the
$\mathsf{DAG}$ class. Note that both $\mathsf{2WP}$ and $\mathsf{DWT}$
generalize $\mathsf{1WP}$ and are incomparable; $\mathsf{PT}$ generalizes both
$\mathsf{2WP}$ and $\mathsf{DWT}$; $\mathsf{DAG}$ generalizes $\mathsf{PT}$;
$\mathsf{Conn}$ generalizes $\mathsf{DAG}$ (see Figure 2 of [7]).

### Boolean Provenance.

We use the notion of Boolean provenance, or simply provenance [19, 3, 29], to
show both upper and lower bounds. Let $G=(V_{G},E_{G},\lambda_{G})$ and
$H=(V_{H},E_{H},\lambda_{H})$ be graphs. For $a_{i}\in V_{G}$ and $b_{i}\in
V_{H}$, denote by $\mathsf{Prov}^{G}_{H}(a_{1}\colonequals
b_{1},\dots,a_{n}\colonequals b_{n})$ the function mapping every valuation
$\nu$ of $E_{G}$ to $1$ (true) or $0$ (false), depending on whether $H$ admits
a homomorphism $h$ from $G$ to the subgraph $\\{e\in H\ |\
\nu(e)=1\\}\subseteq H$ such that $h(a_{i})=b_{i}$ for all $1\leq i\leq n$.
When no constraints on the homomorphism are given, we simply write
$\mathsf{Prov}^{G}_{H}$, and call this function the provenance of $G$ on $H$.
For our lower bounds, we will often seek to represent Boolean formulas as the
provenance of queries on graphs:

######  Definition 2.1.

Given a Boolean formula $\phi$ on variables $x_{1},\ldots,x_{n}$, two graphs
$G$ and $H$, and an $n$-tuple $(e_{1},\ldots,e_{n})$ of pairwise distinct
edges of $H$, we say that $\mathsf{Prov}^{G}_{H}$ _represents_ $\phi$ on
$(e_{1},\ldots,e_{n})$ if the following is true: renaming the variables
$e_{1},\ldots,e_{n}$ of $\mathsf{Prov}^{G}_{H}$ to $x_{1},\ldots,x_{n}$, and
fixing the other variables to be $1$, then we obtain exactly $\phi$.

### Circuits and Knowledge Compilation.

We consider representations of Boolean functions in terms of non-deterministic
(ordered) binary decision diagrams, as well as decomposable circuits, which we
define below.

A non-deterministic binary decision diagram (nBDD) on a set of variables
$V=\\{v_{1},\dots,v_{n}\\}$ is a rooted DAG $D$ whose nodes carry a label in
$V\sqcup\\{0,1,\lor\\}$ and whose edges can carry an optional label in
$\\{0,1\\}$, subject to the following requirements:

  1. 1.

there are exactly two leaves (called sinks), one labelled by $1$ (the
$1$-sink), and the other by $0$ (the _$0$ -sink_);

  2. 2.

internal nodes are labelled either by $\lor$ (called an _$\lor$ -node_) or by
a variable of $V$ (called a _decision node_); and

  3. 3.

each decision node has exactly two outgoing edges, labelled $0$ and $1$; the
outgoing edges of $\lor$-nodes are unlabelled.

The size $|D|$ of $D$ is its number of edges. Let $\nu$ be a valuation of $V$,
and let $\pi$ be a path in $D$ going from the root to one of the sinks. We say
that $\pi$ is compatible with $\nu$ if for every decision node $n$ of the
path, letting $v\in V$ be the variable labelling $n$, then $\pi$ passes
through the outgoing edge of $n$ labelled with $\nu(v)$. In particular, no
constraints are imposed at $\lor$-nodes; thus, we may have that multiple paths
are compatible with a single valuation. The nBDD $D$ _represents_ a Boolean
function, also written $D$ by abuse of notation, which is defined as follows:
for each valuation $\nu$ of $V$, we set $D(\nu)\colonequals 1$ if there exists
a path $\pi$ from the root to the $1$-sink of $D$ that is compatible with
$\nu$, and set $D(\nu)\colonequals 0$ otherwise. Given an nBDD $D$ over
variables $V$, we denote by $\mathsf{Mods}(D)$ the set of satisfying
valuations $\nu$ of $D$ such that $D(\nu)=1$, and by $\mathsf{MC}(D)$ the
number $|\mathsf{Mods}(D)|$ of such valuations. Further, given a rational
probability function $w:V\rightarrow[0,1]$ on the variables of $V$, define
$\mathsf{WMC}(D,w)$ to be the probability that a random valuation $\nu$
satisfies $F$, that is,
$\mathsf{WMC}(D,w)=\sum_{\nu\in\mathsf{Mods}(D)}\prod_{x\in
V\text{\leavevmode\nobreak\ s.t.\leavevmode\nobreak\ }\nu(x)=1}w(x)\prod_{x\in
V\text{\leavevmode\nobreak\ s.t.\leavevmode\nobreak\
}\nu(x)=0}\left(1-w(x)\right)$.

In this paper, we primarily focus on a subclass of nBDDs called non-
deterministic ordered binary decision diagrams (nOBDDs). An nOBDD $D$ is an
nBDD for which there exists a strict total order $\prec$ on the variables $V$
such that, for any two decision nodes $n\neq n^{\prime}$ such that there is a
path from $n$ to $n^{\prime}$, then, letting $v$ and $v^{\prime}$ be the
variables that respectively label $n$ and $n^{\prime}$, we have $v\prec
v^{\prime}$. This implies that, along any path going from the root to a sink,
the sequence of variables will be ordered according to $V$, with each variable
occurring at most once. We use nOBDDs because they admit tractable approximate
counting of their satisfying assignments, as we discuss later.

We also show lower bounds on a class of _circuits_ , called _decomposable
negation normal form_ (DNNF) circuits. A _circuit_ on a set of variables $V$
is a directed acyclic graph $C=(G,W)$, where $G$ is a set of _gates_ , where
$W\subseteq G\times G$ is a set of edges called _wires_ , and where we
distinguish an _output gate_ $g_{0}\in G$. The _inputs_ of a gate $g\in G$ are
the gates $g^{\prime}$ such that there is a wire $(g^{\prime},g)$ in $W$. The
gates can be labelled with variables of $V$ (called a _variable gate_), or
with the Boolean operators $\lor$, $\land$, and $\neg$. We require that gates
labelled with variables have no inputs, and that gates labelled with $\neg$
have exactly one input. A circuit $C$ defines a Boolean function on $V$, also
written $C$ by abuse of notation. Formally, given a valuation $\nu$ of $V$, we
define inductively the _evaluation_ $\nu^{\prime}$ of the gates of $C$ by
setting $\nu^{\prime}(g)\colonequals\nu(v)$ for a variable-gate $g$ labelled
with variable $v$, and setting $\nu^{\prime}(g)$ for other gates to be the
result of applying the Boolean operators of $g$ to
$\nu^{\prime}(g_{1}),\ldots,\nu^{\prime}(g_{n})$ for the inputs
$g_{1},\ldots,g_{n}$ of $g$. We then define $C(\nu)$ to be
$\nu^{\prime}(g_{0})$ where $g_{0}$ is the output gate of $C$.

The circuit is in _negation normal form_ if negations are only applied to
variables, i.e., for every $\neg$-gate, its input is a variable gate. The
circuit is _decomposable_ if the $\land$-gates always apply to inputs that
depend on disjoint variables: formally, there is no $\land$-gate $g$ with two
distinct inputs $g_{1}$ and $g_{2}$, such that some variable $v$ labels two
variable gates $g_{1}^{\prime}$ and $g_{2}^{\prime}$ with $g_{1}^{\prime}$
having a directed path to $g_{1}$ and $g_{2}^{\prime}$ having a directed path
to $g_{2}$. A _DNNF_ is a circuit which is both decomposable and in negation
normal form. Note that we can translate nOBDDs in linear time to DNNFs, more
specifically to _structured DNNFs_ [4, Proposition 3.8].

### Approximate Weighted Counting for nOBDDs.

Recently, Arenas et al. [9] showed the following result on approximate
counting of satisfying assignments of an nOBDD.

######  Theorem 2.2 (Corollary 4.5 of [8]).

Let $D$ be an nOBDD. Then there exists an FPRAS for computing
$\mathsf{MC}(\Delta)$.

For our upper bounds, we need a slight strengthening of this result to apply
to _weighted model counting_ ($\mathsf{WMC}$) in order to handle
probabilities. This can be achieved by translating the approach used in [33,
Section 5.1] to the nOBDD setting. We thus show (see Appendix A):

######  Theorem 2.3.

Let $D$ be an nOBDD, and $w:\mathsf{vars}(\Delta)\rightarrow[0,1]$ be a
rational probability function defined on the variables appearing in $D$. Then
there exists an FPRAS for computing $\mathsf{WMC}(D,w)$, running in time
polynomial in $|D|$ and $w$.

Table 1: Results on approximation proved in this paper. Key: white ( ) means
that the problem lies in $\mathsf{P}$; light grey ( ) means that it is
$\\#\mathsf{P}$-hard but admits an FPRAS; dark grey ( ) means
$\\#\mathsf{P}$-hardness and non-existence of an FPRAS, assuming
$\mathsf{RP}\neq\mathsf{NP}$. All cells without a reference to a corresponding
proposition are either implied by one of the other results in this paper, or
pertain to exact complexity and were already settled in [7].

(a) Complexity of $\mathsf{PHom_{L}}(\mathcal{G},\mathcal{H})$. | $\mathcal{G}\downarrow$
---
$\mathcal{H}\rightarrow$
| $\mathsf{1WP}$ | $\mathsf{2WP}$ | $\mathsf{DWT}$ |  $\mathsf{PT}$ | $\mathsf{DAG}$ |  $\mathsf{Conn}$
$\mathsf{1WP}$ |  |  |  |  | 3.1 |  3.3
$\mathsf{2WP}$ |  |  | 3.7 |  |  |
$\mathsf{DWT}$ |  |  | 3.5 |  |  |
$\mathsf{PT}$ |  |  |  |  |  |

(b) Complexity of $\mathsf{PHom_{\centernot L}}(\mathcal{G},\mathcal{H})$. | $\mathcal{G}\downarrow$
---
$\mathcal{H}\rightarrow$
| $\mathsf{1WP}$ | $\mathsf{2WP}$ | $\mathsf{DWT}$ |  $\mathsf{PT}$ | $\mathsf{DAG}$ |  $\mathsf{Conn}$
$\mathsf{1WP}$ |  |  |  |  | 4.1 | ?
$\mathsf{2WP}$ |  |  |  | 4.3 |  |
$\mathsf{DWT}$ |  |  |  |  | 4.2 | ?
$\mathsf{PT}$ |  |  |  |  |  |

##  3 Results in the Labelled Setting

We now move on to the presentation of our results. We start with the labelled
setting of probabilistic graph homomorphism in which the fixed signature
$\sigma$ of the query and instance graph contains more than one label
($|\sigma|>1$). Our results are summarized in Table 1(a).

###  $\bm{\mathsf{1WP}}$ on $\bm{\mathsf{DAG}}$.

We start by showing the tractability of approximation for
$\mathsf{PHom_{L}}(\mathsf{1WP},\mathsf{DAG})$, which also implies
tractability of approximation for
$\mathsf{PHom_{L}}(\mathsf{1WP},\mathsf{PT})$, since
$\mathsf{PT}\subseteq\mathsf{DAG}$.

######  Proposition 3.1.

$\mathsf{PHom_{L}}(\mathsf{1WP},\mathsf{DAG})$ is $\\#\mathsf{P}$-hard already
in data complexity, but it admits an FPRAS.

For $\\#\mathsf{P}$-hardness, the result already holds in the unlabelled
setting, so it will be shown in Section 4 (see Proposition 4.1). Hence, we
focus on the upper bound. We rely on the notion of a _topological ordering_ of
the edges of a directed acyclic graph $H=(V,E)$: it is simply a strict total
order $(E,\prec)$ with the property that for every consecutive pair of edges
$e_{1}=(a_{1},a_{2})$ and $e_{2}=(a_{2},a_{3})$, we have that $e_{1}\prec
e_{2}$. Let us fix such an ordering.

######  Proof 3.2 (Proof of Proposition 3.1).

We will show that every $\mathsf{1WP}$ query on a $\mathsf{DAG}$ instance
admits an nOBDD representation of its provenance, which we can compute in
combined polynomial time. We can then apply Theorem 2.3, from which the result
follows. Let $G=a_{1}\xrightarrow{R_{1}}\dots\xrightarrow{R_{m}}a_{m+1}$ be
the input path query, and $H$ the instance graph. We make the following claim:

######  Claim 1.

For every $v\in H$, we can compute in time $O(|G|\times|H|)$ an nOBDD
representing $\mathsf{Prov_{L}}^{G}_{H}(a_{1}\colonequals v)$ which is ordered
by the topological ordering $\prec$ fixed above.

Writing $H=(V,E)$, we build an nBDD $D$ consisting of the two sinks and of the
following nodes:

  * •

$|V|\times|G|$ $\lor$-nodes written $n_{u,i}$ for $u\in V$ and $1\leq i\leq
m$; and

  * •

$|E|\times|G|$ decision nodes written $d_{e,i}$ for $e\in E$ and $1\leq i\leq
m$ which test the edge $e$.

Each $\lor$-node $n_{u,i}$ for $u\in V$ and $1\leq i\leq m$ has outgoing edges
to each $d_{e,i}$ for every edge $e$ emanating from $u$ which is labelled
$R_{i}$. For each decision node $d_{e,i}$, letting $w$ be the target of edge
$e$, then $d_{e,i}$ has an outgoing $0$-edge to the $0$-sink and an outgoing
$1$-edge to either $n_{w,i+1}$ if $i<m$ or to the $1$-sink if $i=m$. The root
of the nBDD is the node $n_{v,1}$.

This construction clearly respects the time bound. To check correctness of the
resulting nBDD, it is immediate to observe that, for any path from the root to
a sink, the sequence of decision nodes traversed is of the form
$d_{e_{1},1},\ldots,d_{e_{k},k}$ where the $e_{1},\ldots,e_{k}$ form a path of
consecutive edges starting at $v$ and successively labelled
$R_{1},\ldots,R_{k}$. This implies that the nBDD is in fact an nOBDD ordered
by $\prec$. Further, such a path reaches the $1$-sink iff $k=m$ and all
decisions are positive, which implies that whenever the nOBDD accepts a
subgraph $H^{\prime}$ of $H$ then indeed $H^{\prime}$ contains a match of $G$
mapping $a_{1}$ to $v$. For the converse direction, we observe that, for any
subgraph $H^{\prime}$ of $H$ containing a match of $G$ mapping $a_{1}$ to $v$,
then, letting $e_{1},\ldots,e_{m}$ be the successive edges traversed in the
match of $G$, there is a path from the root of $D$ to the $1$-sink which tests
these edges in order. This establishes correctness and concludes the proof of
the claim. Now observe that
$\mathsf{Prov_{L}}^{G}_{H}=\mathsf{Prov_{L}}^{G}_{H}(a_{1}\colonequals v_{1})\
\lor\ \cdots\ \lor\ \mathsf{Prov_{L}}^{G}_{H}(a_{1}\colonequals v_{n})$, where
$v_{1},\dots,v_{n}$ are precisely the vertices of $H$. Thus, it suffices to
simply take the disjunction of each nOBDD obtained using the process above
across every vertex in $H$, which yields in linear time the desired nOBDD.
From here we can apply Theorem 2.3, concluding the proof.

###  $\bm{\mathsf{1WP}}$ on arbitrary graphs.

We show, however, that tractability of approximation does not continue to hold
when relaxing the instance class from $\mathsf{DAG}$ to arbitrary connected
graphs. This also implies that more expressive classes of query graphs—such as
$\mathsf{2WP}$, $\mathsf{DWT}$, and $\mathsf{PT}$ also cannot be tractable to
approximate on $\mathsf{Conn}$ instances.

######  Proposition 3.3.

$\mathsf{PHom_{L}}(\mathsf{1WP},\mathsf{Conn})$ does not admit an FPRAS unless
$\mathsf{RP}=\mathsf{NP}$.

######  Proof 3.4.

Our result hinges on the following claim:

######  Claim 2.

Let $d>1$ be a constant. Given a monotone 2-CNF formula $\phi$ on $n$
variables where each variable occurs in at most $d$ clauses, we can build in
time $O(|\phi|)$ a $\mathsf{1WP}$ $G_{\phi}$ and $\mathsf{Conn}$ graph
$H_{\phi}$ containing edges $(e_{1},\ldots,e_{n})$ such that
$\mathsf{Prov}^{G_{\phi}}_{H_{\phi}}$ represents $\phi$ on
$(e_{1},\ldots,e_{n})$.

Let $\phi=\bigwedge_{1\leq i\leq m}(X_{f_{1}(i)}\lor X_{f_{2}(i)})$ be the
input CNF instance over the variables $\\{X_{1},\dots,X_{n}\\}$. As we are in
the labelled setting, let $U$ and $R$ be two distinct labels from the
signature. Define the $\mathsf{1WP}$ query graph $G_{\phi}$ to be
$\xrightarrow{U}\left(\xrightarrow{R}^{d+2}\xrightarrow{U}\right)^{m}$. The
instance $\mathsf{Conn}$ graph $H_{\phi}$ is defined in the following way:

  * •

For all $1\leq i\leq n$, add an edge $a_{i}\xrightarrow{R}b_{i}$.

  * •

Add an edge $c_{0}\xrightarrow{U}d_{0}$ and for each clause $1\leq j\leq m$,
an edge $c_{j}\xrightarrow{U}d_{j}$.

  * •

For each clause $1\leq j\leq m$ and variable $X_{i}$ occurring in that clause,
let $p$ be the number of this occurrence of $X_{i}$ in the formula (i.e., the
occurrence of $X_{i}$ in the $j$-th clause is the $p$-th occurrence of
$X_{i}$), with $1\leq p\leq d$ by assumption on $\phi$. Then add a path of
length $p$ of $R$-edges from $d_{j-1}$ to $a_{i}$ and a path of length
$(d+1)-p$ of $R$-edges from $b_{i}$ to $c_{j}$.

The construction of $G_{\phi}$ and $H_{\phi}$ is in $O(|\phi|)$. Furthermore,
notice the following ($\star$). For any $1\leq i\leq n$, the edge
$e=a_{i}\xrightarrow{R}b_{i}$ has at most $d$ incoming $R$-paths and $d$
outgoing $R$-paths; the outgoing paths have pairwise distinct _length_ (i.e.,
the number of edges until the next edge is a $U$-edge), and likewise for the
incoming paths. What is more, each incoming $R$-path of length $p$ corresponds
to an outgoing path of length $(d+1)-p$ and together they connect some
$d_{j-1}$ to some $c_{j}$ via the edge $e$, where the $j$-th clause contains
variable $X_{i}$.

Now, define $(e_{1},\dots,e_{n})$ to be precisely the edges of the form
$a_{i}\xrightarrow{R}b_{i}$ for every $1\leq i\leq n$. Intuitively, the
presence or absence of each of these edges corresponds to the valuation of
each variable in $\phi$. We claim that $\mathsf{Prov}^{G_{\phi}}_{H_{\phi}}$
represents $\phi$ on $(e_{1},\ldots,e_{n})$. It will suffice to show that
there is a bijection between the satisfying valuations of $\phi$, and the
subgraphs of $H_{\phi}$ that both (i) contain all the edges not in
$(e_{1},\dots,e_{n})$, as these are fixed to $1$, and (ii) admit a
homomorphism from $G_{\phi}$.

Indeed, consider the bijection defined in the obvious way: keep the edge
$a_{i}\xrightarrow{R}b_{i}$ iff $X_{i}$ is assigned to true in the valuation.
First suppose that some valuation of $\\{X_{1},\dots,X_{n}\\}$ satisfies
$\phi$. Then, for each clause $1\leq j\leq m$, there is a variable in the
clause which evaluates to true. We build a match of $G_{\phi}$ on the
corresponding possible world of $H_{\phi}$ by mapping the $j$-th $U$-edge to
$c_{j}\xrightarrow{U}d_{j}$ for all $0\leq j\leq m$, and mapping the $R$-paths
for each $1\leq j\leq m$ by picking a variable $X_{i}$ witnessing that the
clause is satisfied and going via the path of length
$1+\left(p\right)+\left(\left(d+1\right)-p\right)=d+2$ that uses the edge
$a_{i}\xrightarrow{R}b_{i}$, which is present by assumption.

Conversely, assume that we have a match of $G_{\phi}$ on a possible world of
$H_{\phi}$. We show that the corresponding valuation satisfies $\phi$.
Consider the edge $c_{j}\xrightarrow{U}d_{j}$ to which the first $U$-edge is
mapped. The $R$-path that follows must be mapped to a path from $d_{j}$ to
some $a_{i}$, and then take the edge $a_{i}\xrightarrow{R}b_{i}$, whose
presence witnesses that the corresponding variable $X_{i}$ is true. But
importantly, in order for the path to have length precisely $d+2$ before
reaching the next $U$-edge, it must be the case that the length of the path
before and after the edge $a_{i}\xrightarrow{R}b_{i}$ sums up to $d+1$. As a
result of ($\star$), this is only possible by taking a path that leads to
$c_{j+1}\xrightarrow{U}d_{j+1}$, and so we know that variable $X_{i}$ occurs
in the $j$-th clause so that clause is satisfied. Repeating the argument shows
that all clauses from the $j$-th onwards are satisfied, and as we have $m+1$
$U$-edges in the graph $H_{\phi}$ and $m+1$ $U$-edges in the graph $G_{\phi}$
we know that in fact we must have mapped the first $U$-edge to the first
$U$-edge (i.e., $j=0$), and all clauses are satisfied. By [30, Theorem 2],
counting the independent sets of a graph of maximal degree $6$ admits an FPRAS
only if $\mathsf{RP}=\mathsf{NP}$. It is not hard to see that this problem is
equivalent to counting satisfying assignments of a monotone 2-CNF formula in
which a variable can appear in up to $6$ clauses (see, for example, [24,
Proposition 1.1]). Thus, we can apply Claim 2 above for the class of formulas
in which $d=6$ to obtain (deterministic) graphs $G_{\phi}$ and $H_{\phi}$, and
then build a probabilistic graph $H_{\phi}^{\prime}$ identical to $H_{\phi}$,
in which the edges $(e_{1},\dots,e_{n})$ are assigned probability $0.5$ and
all other edges probability $1$, giving the desired reduction.

###  $\bm{\mathsf{DWT}}$ on $\bm{\mathsf{DWT}}$.

Having classified the cases of one-way path queries ($\mathsf{1WP}$) on all
instances classes considered, we turn to more expressive queries. The next two
query classes to consider are two-way path queries ($\mathsf{2WP}$) and
downwards trees queries ($\mathsf{DWT}$). For these query classes, exact
computation on $\mathsf{2WP}$ instances is tractable by [7], so the first case
to classify is that of $\mathsf{DWT}$ instances. Exact computation is
intractable in this case by [7], and we show here that, unfortunately,
approximation is intractable as well, so that the border for exact
tractability coincides with that for approximate tractability. We first focus
on $\mathsf{DWT}$ queries:

######  Proposition 3.5.

$\mathsf{PHom_{L}}(\mathsf{DWT},\mathsf{DWT})$ does not admit an FPRAS unless
$\mathsf{RP}=\mathsf{NP}$.

######  Proof 3.6.

Our result hinges on the following, whose proof adapts [25, Proposition
2.4.3]:

######  Claim 3.

Given a monotone 2-CNF formula $\phi$ on $n$ variables, we can build in time
$O(|\phi|\log|\phi|)$ $\mathsf{DWT}$ graphs $G_{\phi}$ and $H_{\phi}$, with
the latter containing edges $(e_{1},\ldots,e_{n})$ such that
$\mathsf{Prov}^{G_{\phi}}_{H_{\phi}}$ represents $\phi$ on
$(e_{1},\ldots,e_{n})$.

Let $\phi=\bigwedge_{1\leq i\leq m}(X_{f_{1}(i)}\lor X_{f_{2}(i)})$ be the
input CNF instance over the variables $\\{X_{1},\dots,X_{n}\\}$. We let
$L=\lceil\log_{2}m\rceil$ be the number of bits needed to write clause numbers
in binary. As we are in the labelled setting, let $0$ and $1$ be two distinct
labels from the signature. Construct the query graph $G_{\phi}$ as follows:

  * •

For all $1\leq i\leq m$, add an edge $z\xrightarrow{0}x_{i}$.

  * •

For each $1\leq i\leq m$, letting $b_{1}\cdots b_{L}$ be the clause number $i$
written in binary, add a path of $L$ edges
$x_{i}\xrightarrow{b_{1}}y_{i,1}\xrightarrow{b_{2}}\ldots\xrightarrow{b_{L-1}}y_{i,L}\xrightarrow{b_{L}}y_{i,L}$.

Now, construct the $\mathsf{DWT}$ instance $H_{\phi}$ as follows:

  * •

For all $1\leq i\leq n$, add the edges $a\xrightarrow{0}c_{i}$.

  * •

For all $1\leq i\leq n$ and $1\leq j\leq m$ such that $X_{i}$ occurs in the
$j$-th clause of $\phi$ (i.e., $X_{i}$ is in $f_{1}^{-1}(j)$ or
$f_{2}^{-1}(j)$), letting $b_{1}\cdots b_{L}$ be the clause number $j$ written
in binary, add a path of $L$ edges
$c_{i}\xrightarrow{b_{1}}d_{i,j,1}\xrightarrow{b_{2}}\ldots\xrightarrow{b_{L-1}}d_{i,j,L-1}\xrightarrow{b_{L}}d_{i,j,L+1}$.

It is clear that $G_{\phi}\in\mathsf{DWT}$, $H_{\phi}\in\mathsf{DWT}$, and
that both graphs can be built in time $O(|\phi|\log|\phi|)$. Now, define
$(e_{1},\dots,e_{n})$ to be the edges of the form $a\xrightarrow{0}c_{i}$ for
every $1\leq i\leq n$.

We claim that $\mathsf{Prov}^{G_{\phi}}_{H_{\phi}}$ represents $\phi$ on
$(e_{1},\ldots,e_{n})$. It suffices to show that there is a bijection between
the satisfying valuations $\nu$ of $\phi$, and the subgraphs of $H_{\phi}$
that both (i) contain all the edges not in $(e_{1},\dots,e_{n})$, as these are
fixed to $1$, and (ii) admit a homomorphism from $G_{\phi}$. Indeed, consider
the bijection defined in the obvious way: keep the edge
$a\xrightarrow{T}c_{i}$ iff $X_{i}$ is assigned to true in the valuation.
First, if there is a homomorphism from $G_{\phi}$ to such a subgraph, then the
root $z$ of the query must be mapped to $a$ (since this is the only element
with outgoing paths of length $L+1$ as prescribed by the query), and then it
is clear that the image of any such homomorphism must take the form of a
$\mathsf{DWT}$ instance that contains, for each clause number $1\leq i\leq m$,
a path of length $L$ representing this clause number. This witnesses that the
valuation $\nu$ makes a variable true which satisfies clause $i$. Hence, $\nu$
is a satisfying assignment of $\phi$. Conversely, for every satisfying
assignment $\nu$, considering the corresponding subgraph of $H_{\phi}$, we can
construct a homomorphism mapping the edges of $G_{\phi}$ to the edges of
$H_{\phi}$, by mapping the path of every clause to a path connected to a
variable that witnesses that this clause is satisfied by $\nu$. The result
then follows by an argument analogous to the one in Proposition 3.3.

###  $\bm{\mathsf{2WP}}$ on $\bm{\mathsf{DWT}}$.

We then move to $\mathsf{2WP}$ queries:

######  Proposition 3.7.

$\mathsf{PHom_{L}}(\mathsf{2WP},\mathsf{DWT})$ does not admit an FPRAS unless
$\mathsf{RP}=\mathsf{NP}$.

This result follows from a general reduction technique from $\mathsf{DWT}$
queries on $\mathsf{DWT}$ instances to $\mathsf{2WP}$ queries on
$\mathsf{DWT}$ instances, which allows us to conclude using the result already
shown on $\mathsf{DWT}$ queries (Proposition 3.5). We note that this technique
could also have been used to simplify the proofs of hardness of exact
computation in [7] and [2]. We claim:

######  Lemma 3.8.

For any $\mathsf{DWT}$ query $G$, we can compute in time $O(|G|)$ a
$\mathsf{2WP}$ query $G^{\prime}$ which is equivalent to $G$ on $\mathsf{DWT}$
instances: for any $\mathsf{DWT}$ $H$, there is a homomorphism from $G$ to $H$
iff there is a homomorphism from $G^{\prime}$ to $H$.

For lack of space, we give only the construction of $G^{\prime}$ here, and
defer the full proof of the correctness of this construction to Appendix B.

######  Proof 3.9.

Let $G$ be a $\mathsf{DWT}$ query. We build $G^{\prime}$ following a tree
traversal of $G$. More precisely, we define the translation inductively as
follows. If $G$ is the trivial query with no edges, then we let the
translation of $G$ be the trivial query with no edges. Otherwise, let $x$ be
the root of $G$, let
$x\xrightarrow{R_{1}}y_{1},\ldots,x\xrightarrow{R_{n}}y_{n}$ be the successive
children, and call $G_{1},\ldots,G_{n}$ the $\mathsf{DWT}$ subqueries of $G$
respectively rooted at $y_{1},\ldots,y_{n}$. We define the translation of $G$
to be
$\xrightarrow{R_{1}}G^{\prime}_{1}\xleftarrow{R_{1}}\cdots\xrightarrow{R_{n}}G^{\prime}_{n}\xleftarrow{R_{n}}$,
where $G_{1}^{\prime},\ldots,G_{n}^{\prime}$ are the respective translations
of $G_{1}$, …, $G_{n}$. This translation is in linear time, and the translated
query has twice as many edges as the original query.

Lemma 3.8 allows us to conclude from Proposition 3.5, as it allows us to
reduce in linear time (in combined complexity) the evaluation of a
$\mathsf{DWT}$ query on a $\mathsf{DWT}$ probabilistic instance to the
evaluation of an equivalent $\mathsf{2WP}$ query on the same instance. This
establishes that any approximation algorithm for $\mathsf{2WP}$ queries on
$\mathsf{DWT}$ instances would give an approximation for $\mathsf{DWT}$
queries on $\mathsf{DWT}$ instances, which by Proposition 3.5 is conditionally
impossible.

These results complete Table 1, concluding the classification of the
complexity of $\mathsf{PHom}$ in the labelled setting: all cases that were
intractable for exact computation are also hard to approximate, with the
notable exception of $\mathsf{1WP}$ queries on $\mathsf{DAG}$ instances.

##  4 Results in the Unlabelled Setting

We now turn to the unlabelled setting of probabilistic graph homomorphism,
where the signature $\sigma$ has only one label ($|\sigma|=1$). Our results
are summarized in Table 1(b): we settle all cases except
$\mathsf{PHom_{\centernot L}}(\mathsf{1WP},\mathsf{Conn})$ and
$\mathsf{PHom_{\centernot L}}(\mathsf{DWT},\mathsf{Conn})$, for which we do
not give an FPRAS or hardness of approximation result. Note that both problems
are $\\#\mathsf{P}$-hard for exact computation [7]. Further, they are in fact
equivalent, because $\mathsf{DWT}$ queries are equivalent to $\mathsf{1WP}$
queries in the unlabelled setting (stated in [7] and reproved as Proposition
4.2 below).

###  $\bm{\mathsf{1WP}}$ on $\bm{\mathsf{DAG}}$.

We start with $\mathsf{1WP}$ queries, and state the following:

######  Proposition 4.1.

$\mathsf{PHom_{\centernot L}}(\mathsf{1WP},\mathsf{DAG})$ is
$\\#\mathsf{P}$-hard already in data complexity, but it admits an FPRAS.

The positive result directly follows from the existence of an FPRAS in the
labelled setting, which we have shown in the previous section (Proposition
3.1). By contrast, the $\\#\mathsf{P}$-hardness does not immediately follow
from previous work, as $\mathsf{DAG}$ queries were not studied in [7]. We can
nevertheless obtain it by inspecting the usual $\\#\mathsf{P}$-hardness proof
of PQE for the CQ $\exists x\,y\leavevmode\nobreak\ R(x),S(x,y),T(y)$ on TID
instances [31]. We give a proof in Appendix C.

###  $\bm{\mathsf{DWT}}$ on $\bm{\mathsf{DAG}}$.

We can easily generalize the above result from $\mathsf{1WP}$ queries to
$\mathsf{DWT}$ queries, given that they are known to be equivalent in the
unlabelled setting:

######  Proposition 4.2 ([7]).

$\mathsf{PHom_{\centernot L}}(\mathsf{DWT},\mathsf{DAG})$ is
$\\#\mathsf{P}$-hard already in data complexity, but admits an FPRAS.

This is implicit in [7, Proposition 5.5]: we give a self-contained proof in
Appendix D.

###  $\bm{\mathsf{2WP}}$ on $\bm{\mathsf{PT}}$.

In contrast to $\mathsf{1WP}$ queries, which are exactly tractable on
$\mathsf{PT}$ instances and admit an FPRAS on $\mathsf{DAG}$ instances,
$\mathsf{2WP}$ queries have no FPRAS already on $\mathsf{PT}$ instances:

######  Proposition 4.3.

$\mathsf{PHom_{\centernot L}}(\mathsf{2WP},\mathsf{PT})$ does not admit an
FPRAS unless $\mathsf{RP}=\mathsf{NP}$.

######  Proof 4.4.

It suffices to prove the claim below, which is the analogue to the unlabelled
setting of Claim 3 after having transformed the query to $\mathsf{2WP}$ via
Lemma 3.8:

######  Claim 4.

Given a monotone 2-CNF formula $\phi$ on $n$ variables, we can build in time
$O(|\phi|\log|\phi|)$ an unlabeled $\mathsf{2WP}$ graph $G_{\phi}$ and
unlabeled $\mathsf{PT}$ graph $H_{\phi}$, with the latter containing edges
$(e_{1},\ldots,e_{n})$ such that $\mathsf{Prov}^{G_{\phi}}_{H_{\phi}}$
represents $\phi$ on $(e_{1},\ldots,e_{n})$.

We show this claim via a general-purpose reduction from the labelled setting
to the unlabelled setting, which works in fact for $\mathsf{Conn}$ queries on
$\mathsf{Conn}$ graphs. This reduction codes labels via specific unlabelled
paths; a similar but ad-hoc technique was used to prove [7, Proposition 5.6]:

######  Lemma 4.5.

For any constant $k\geq 2$, given a $\mathsf{Conn}$ query $G$ and
$\mathsf{Conn}$ graph $H$ on a labelled signature with relation labels
$\\{1,\ldots,k\\}$, we can construct in linear time an unlabelled
$\mathsf{Conn}$ query $G^{\prime}$ and $\mathsf{Conn}$ graph $H^{\prime}$ such
that there is a (labelled) homomorphism from $G$ to $H$ iff there is an
(unlabelled) homomorphism from $G^{\prime}$ to $H^{\prime}$. Further, if $G$
is a $\mathsf{2WP}$ then $G^{\prime}$ is also a $\mathsf{2WP}$, and if $H$ is
a $\mathsf{PT}$ then $H^{\prime}$ is also a $\mathsf{PT}$.

######  Proof 4.6.

We construct $G^{\prime}$ from $G$ and $H^{\prime}$ from $H$ by replacing
every edge by a fixed path that depends on the label of the edge.
Specifically, we consider every edge $x\xrightarrow{i}y$ of the query, where
$x$ is the source, $t$ is the target, and $1\leq i\leq k$ is the label. We
code such an edge in $G^{\prime}$ by a path defined as follows:
$x\rightarrow^{k+3}\leavevmode\nobreak\ \leftarrow\leavevmode\nobreak\
\rightarrow^{i+1}\leavevmode\nobreak\ \leftarrow^{k+2}\leavevmode\nobreak\ y$,
where exponents denote repeated edges and where intermediate vertices are
omitted. We code the instance $H$ to $H^{\prime}$ in the same way. This
process is clearly linear-time, and it is clear that if $G$ is a
$\mathsf{2WP}$ then $G^{\prime}$ is also a $\mathsf{2WP}$, and that if $H$ is
a $\mathsf{PT}$ then $H^{\prime}$ is also a $\mathsf{PT}$. Further, to
establish correctness of the reduction, one direction of the equivalence is
trivial: a homomorphism $h$ from $G$ to $H$ clearly defines a homomorphism
from $G^{\prime}$ to $H^{\prime}$ by mapping the coding in $G^{\prime}$ of
every edge $e$ of $G$ to the coding of the image of $e$ by $h$ in $H^{\prime}$

What is interesting is the converse direction of the equivalence. We establish
it via a claim on homomorphic images of the coding of individual edges: for
any $1\leq i\leq k$, letting $e^{\prime}$ be the coding of an edge
$e=x\xrightarrow{i}y$, for any homomorphism $h^{\prime}$ from $e^{\prime}$ to
$H^{\prime}$, there must exist an edge $f=a\xrightarrow{i}b$ in $H$ such that
$h^{\prime}$ maps $x$ to $a$ and $y$ to $b$. This claim implies the converse
direction of the equivalence: if there is a homomorphism $h^{\prime}$ from
$G^{\prime}$ to $H^{\prime}$, then applying the claim to the restrictions of
$h^{\prime}$ to the coding of each edge of $G$, we see that $h^{\prime}$
defines a function $h$ that maps the vertices of $G$ to vertices of $H$, and
that $h$ is a homomorphism. Hence, all that remains is to prove the claim,
which we do in the rest of the proof.

Consider an edge $e=x\xrightarrow{i}y$ as in the claim statement, and let
$e^{\prime}$ be its coding and $h^{\prime}$ the homomorphism mapping
$e^{\prime}$ to $H^{\prime}$. Observe that, in $H^{\prime}$, the only directed
paths of length $k+3$ are the first $k+3$ edges of the coding of edges of $H$.
(This hinges on the fact that the paths of length $k+3$ defined in the coding
of edges of $H$ are never adjacent in $H^{\prime}$ to another edge that goes
in the same direction, even across multiple edges, and no matter the
directions of edges in $H$.) This means that, considering the directed path
$\rightarrow^{k+3}$ at the beginning of $e^{\prime}$, there must be an edge
$f=a\xrightarrow{j}b$ of $H$, with coding $f^{\prime}$ in $H^{\prime}$, such
that the source $x$ of $e$ is mapped to the source $a$ of $f$, and the first
$k+3$ edges of $e^{\prime}$ are mapped to the first $k+3$ edges of
$f^{\prime}$. What remains to be shown is that $i=j$ and that $y$ is mapped to
$b$.

To this end, we continue studying what can be the image of $e^{\prime}$ into
$f^{\prime}$. After the directed path $\rightarrow^{k+3}$, the next edge
$\leftarrow$ of $e^{\prime}$ must have been mapped forward to the next edge
$\leftarrow$ of $f^{\prime}$: indeed, it cannot be mapped backwards on the
last edge of the preceding path $\rightarrow^{k+3}$ because $k+3>1$ and
$i+1>1$ so the next edges $\rightarrow^{i+1}$ would then have no image. Then
the next directed path $\rightarrow^{i+1}$ of $e^{\prime}$ is mapped in
$f^{\prime}$, necessarily forward because we fail if we map the first edge
backwards: this implies that there at least as many edges going in that
direction in $f^{\prime}$ as there are in $e^{\prime}$, i.e., $i\leq j$. Now,
the last path $\leftarrow^{k+2}$ of $e^{\prime}$ cannot be mapped backwards
because $k+2>i+1$, so we must map it forwards in $f^{\prime}$: for this to be
possible, we must have reached the end of the directed path
$\rightarrow^{j+1}$ in $f^{\prime}$, so that we have $j=i$. We are now done
reading $e^{\prime}$ and $f^{\prime}$, so we have indeed mapped $y$ to $b$.
This, along with $i=j$, establishes that the claim is true, and concludes the
proof.

We can thus prove Claim 4, starting from Claim 3 and translating it first via
Lemma 3.8 and then via Lemma 4.5. Using the same argument as in Proposition
3.3, we conclude the proof of Proposition 4.3.

##  5 DNNF Lower Bounds

In this section, we investigate how to represent the provenance of the query-
instance pairs that we consider. More specifically, we study whether there
exist polynomially-sized representations in tractable circuit classes of
Boolean provenance functions $\mathsf{Prov}^{G}_{H}$, for $G\in\mathcal{G}$
and $H\in\mathcal{H}$ in the graph classes studied in this paper. Certainly,
for every graph class $\mathcal{G}$ and $\mathcal{H}$, the (conditional) non-
existence of an FPRAS for $\mathsf{PHom}(\mathcal{G},\mathcal{H})$ implies
that, conditionally, we cannot compute nOBDD representations of provenance in
polynomial time combined complexity—as otherwise we could obtain an FPRAS via
Theorem 2.3. In fact, beyond nOBDDs, it follows from [9, Theorem 6.3] that,
conditionally, we cannot tractably compute provenance representations even in
the more general class of _structured DNNFs_. Indeed, as for nOBDDs, fixed
edges in the reductions can be handled by conditioning [27, Proposition 4].

However, even in settings where there is conditionally no combined FPRAS, it
could be the case that there are polynomial-_sized_ tractable circuits that
are difficult to compute, or that we can tractably compute circuits in a more
general formalism such as _unstructured_ DNNF circuits. The goal of this
section is to give a negative answer to these two questions, for all of the
non-approximable query-instance class pairs studied in Sections 3 and 4.

Specifically, we show moderately exponential lower bounds on the size of DNNF
circuits for infinite families of graphs taken from these classes. Remember
that DNNF is arguably the most general knowledge compilation circuit class
that still enjoys some tractable properties [16]. Hence, these lower bounds
imply that no tractable provenance representation exists in other tractable
subclasses of DNNFs, e.g., structured DNNFs [27], or Decision-DNNFs [10]. We
also emphasize that, unlike the intractability results of Sections 3 and 4
which assumed $\mathsf{RP}\neq\mathsf{NP}$, all of the DNNF lower bounds given
here are unconditional.

We first show a strongly exponential lower bound for labelled $\mathsf{1WP}$
on $\mathsf{Conn}$ instances:

######  Proposition 5.1.

There is an infinite family $G_{1},G_{2},\ldots$ of labelled $\mathsf{1WP}$
queries and an infinite family $H_{1},H_{2},\ldots$ of labelled
$\mathsf{Conn}$ instances such that, for any $i>0$, any DNNF circuit
representing the Boolean function $\mathsf{Prov}^{G_{i}}_{H_{i}}$ has size
$2^{\Omega(|G_{i}|+|H_{i}|)}$.

######  Proof 5.2.

By _treewidth_ of a monotone 2-CNF formula, we mean the treewidth of the graph
on the variables whose edges correspond to clauses in the expected way; and by
_degree_ we mean the maximal number of clauses in which any variable occurs.
Let us consider an infinite family $\phi_{1},\phi_{2},\ldots$ of monotone
2-CNF formulas of constant degree $d=3$ whose treewidth is linear in their
size: this exists by [17, Proposition 1, Theorem 5]. We accordingly know by
[4, Corollary 8.5] that any DNNF computing $\phi_{i}$ must have size
$2^{\Omega(|\phi_{i}|)}$ for all $i>1$. Using Claim 2, we obtain infinite
families $G_{1},G_{2},\ldots$ of $\mathsf{1WP}$ and $H_{1},H_{2},\ldots$ of
$\mathsf{Conn}$ graphs such that $\mathsf{Prov}^{G_{i}}_{H_{i}}$ represents
$\phi_{i}$ on some choice of edges, and we have
$|G_{i}|+|H_{i}|=O(|\phi_{i}|)$ for all $i>0$ (from the running time bound).
Now, any representation of $\mathsf{Prov_{L}}^{G_{i}}_{H_{i}}$ as a DNNF can
be translated in linear time to a representation of $\phi_{i}$ as a DNNF of
the same size, simply by renaming the edges $(e_{1},\ldots,e_{n})$ to the
right variables, and replacing all other variables by the constant $1$. This
means that the lower bound on the size of DNNFs computing $\phi_{i}$ also
applies to DNNFs representing $\mathsf{Prov}^{G_{i}}_{H_{i}}$, i.e., they must
have size at least $2^{\Omega(|\phi_{i}|)}$, hence
$2^{\Omega(|G_{i}|+|H_{i}|)}$ as we claimed.

We now present lower bounds for the remaining non-approximable query-instance
class pairs, which are not exponential but rather moderately exponential. This
is because our encoding of CNFs into these classes (specifically, Claim 3, and
its images by Lemma 3.8 and Lemma 4.5) do not give a linear, but rather
linearithmic bound. We leave to future work the question of proving strongly
exponential lower bounds for these classes, like we did in Proposition 5.1.

######  Proposition 5.3.

For any $\epsilon>0$, there is an infinite family $G_{1},G_{2},\ldots$ of
labelled $\mathsf{DWT}$ queries and an infinite family $H_{1},H_{2},\ldots$ of
labelled $\mathsf{DWT}$ instances such that, for any $i>0$, any DNNF circuit
representing the Boolean function $\mathsf{Prov}^{G_{i}}_{H_{i}}$ has size at
least $2^{\Omega\left(\left(|G_{i}|+|H_{i}|\right)^{1-\epsilon}\right)}$.

######  Proof 5.4.

The proof is identical to that of Proposition 5.1, except that we apply Claim
3: for all $i>0$, $|G_{i}|+|H_{i}|=O(|\phi_{i}|\log{|\phi_{i}|})$. We perform
a change of variables: if we write $y=|\phi_{i}|\log|\phi_{i}|$, then we can
show that $|\phi_{i}|=e^{W(y)}$, where $W$ denotes the Lambert $W$ function
[12]; equivalently $|\phi_{i}|=y/W(y)$ as the $W$ function satisfies
$W(z)e^{W(z)}=z$ for all $z>0$. Thus, the lower bound of
$2^{\Omega(|\phi_{i}|)}$ on DNNF representations of $\phi_{i}$ implies that
any DNNF for $\mathsf{Prov}^{G_{j}}_{H_{j}}$ has size at least
$2^{\Omega\left(\frac{|G_{i}|+|H_{i}|}{W(|G_{i}|+|H_{i}|)}\right)}$. In
particular, as $W$ grows more slowly than $n^{\epsilon}$ for any $\epsilon>0$,
this gives a bound of
$2^{\Omega\left(\left(|G_{i}|+|H_{i}|\right)^{1-\epsilon}\right)}$ for
sufficiently large $\phi_{j}$.

The proof for the following two claims are analogous to that of Proposition
5.3, but using Lemma 3.8 (for the first result) and Claim 4 (for the second
result):

######  Proposition 5.5.

For any $\epsilon>0$, there is an infinite family $G_{1},G_{2},\ldots$ of
labelled $\mathsf{2WP}$ queries and an infinite family $H_{1},H_{2},\ldots$ of
labelled $\mathsf{DWT}$ instances such that, for any $i>0$, any DNNF circuit
representing the Boolean function $\mathsf{Prov}^{G_{i}}_{H_{i}}$ has size at
least $2^{\Omega\left(\left(|G_{i}|+|H_{i}|\right)^{1-\epsilon}\right)}$.

######  Proposition 5.6.

For any $\epsilon>0$, there is an infinite family $G_{1},G_{2},\ldots$ of
unlabelled $\mathsf{2WP}$ queries and an infinite family $H_{1},H_{2},\ldots$
of unlabelled $\mathsf{PT}$ instances such that, for any $i>0$, any DNNF
circuit representing the Boolean function $\mathsf{Prov}^{G_{i}}_{H_{i}}$ has
size at least
$2^{\Omega\left(\left(|G_{i}|+|H_{i}|\right)^{1-\epsilon}\right)}$.

We finish by remarking that all of the lower bounds above apply to acyclic
query classes (i.e., queries of treewidth 1), for which non-probabilistic
query evaluation is well-known to be linear in combined complexity [35]. Thus,
these results give an interesting example of query classes for which query
evaluation is in linear-time combined complexity, but computing even a DNNF
representation of query provenance is (moderately) exponential.

##  6 Consequences

In this section, we consider some corollaries and extensions to the results
above.

### Optimality of a Previous Result.

Recall from the introduction that, as was shown in [33], PQE for self-join-
free conjunctive queries of bounded hypertree width admits a combined FPRAS
(in the general setting of probabilistic databases, rather than probabilistic
graphs): See 1.1 Can a stronger result be achieved? Our Proposition 4.3
immediately implies the following:

######  Corollary 6.1.

Assuming $\mathsf{RP}\neq\mathsf{NP}$, even on a fixed signature consisting of
a single binary relation there is no FPRAS to approximate the probability of
an input treewidth-1 CQ on an input treewidth-1 TID instance.

Hence, tractability no longer holds with self-joins. So, as unbounded
hypertree width queries are intractable in combined complexity even for
deterministic query evaluation, we have:

######  Corollary 6.2.

The result in Theorem 1.1 is optimal in the following sense: relaxing either
the self-join-free or bounded-hypertree-width condition on the query implies
the non-existence of a combined FPRAS, unless $\mathsf{RP}=\mathsf{NP}$.

### Network Reliability.

The two-terminal network reliability problem asks the following: given a graph
with probabilistic edges and with source and target vertices $s$ and $t$,
compute the probability that $s$ and $t$ remain connected, assuming
independence across edges. Valiant showed that this problem is
$\\#\mathsf{P}$-complete [32, Theorem 1], and Provan and Ball showed that this
holds already on directed acyclic graphs [28, Table 1]. Hardness also holds
for the related problem of _all-terminal reliability_ [28, Table 1], which
asks for the probability that the probabilistic graph remains connected as a
whole. Given the inherent $\\#\mathsf{P}$-hardness of these problems,
subsequent research has focused on developing tractable approximations.

Although significant progress has been made on FPRASes for all-terminal
(un)reliability [18, 22], designing an FPRAS for two-terminal reliability has
remained open. This question was even open for the restricted case of directed
acyclic graphs; indeed, it was explicitly posed as an open problem by
Zenklusen and Laumanns [36]. We now point out that the nOBDD construction of
Proposition 3.1 implies an FPRAS for two-terminal reliability on DAGs, again
by leveraging the approximate counting result of Arenas et al. [8]:

######  Theorem 6.3.

There exists an FPRAS for the two-terminal network reliability problem over
directed acyclic graphs.

######  Proof 6.4.

Given as input an unlabelled probabilistic $\mathsf{DAG}$ instance $H=(V,E)$
and two distinguished source and target vertices $s$ and $t\in V$, construct
the labelled $\mathsf{DAG}$ instance $G^{\prime}=(V,E,\lambda)$ as follows.
All vertices and edges are identical to that of $G$, but every edge of the
form $(s,x)$ emanating from $s$ is assigned label $\lambda((s,x))=R_{s}$,
every edge $(x,t)$ directed towards $t$ is assigned label
$\lambda((x,t))=R_{t}$, and every other edge $(x,y)$ is assigned the label
$\lambda((x,y))=R$. In the case that $(s,t)\in E$, then assign
$\lambda((s,t))=R_{s}$.

Now, by the result in Proposition 3.1, we can construct an nOBDD for each of
the following $|E|$ different labelled $\mathsf{1WP}$ queries:
$\xrightarrow{R_{s}}$, $\xrightarrow{R_{s}}\xrightarrow{R_{t}}$,
$\xrightarrow{R_{s}}\xrightarrow{R}\xrightarrow{R_{t}}$, …,
$\xrightarrow{R_{s}}\left(\xrightarrow{R}\right)^{|E|-2}\xrightarrow{R_{t}}$.
All of the nOBDDs have the same ordering (given by a topological ordering of
the edges of $G$), so we may take their disjunction to obtain a (complete)
nOBDD $D$ in linear time, whose accepting paths are in bijection with the
$(s,t)$-connected valuations of the edges in $G$. From here we conclude by
applying Theorem 2.3.

##  7 Conclusions and Future Work

We studied the existence and non-existence of combined approximation
algorithms for the PQE problem, as well as the existence of polynomially-sized
tractable circuit representations of provenance, under the lens of combined
complexity.

We see several potential directions for future work. First, it would be
interesting to see if the results in Proposition 3.1 and Theorem 6.3 can be
extended beyond $\mathsf{DAG}$ instances: graph classes of bounded DAG-width
[11] could be a possible candidate here. We also leave open the problem of
filling in the two remaining gaps in Table 1. Namely, we would like to obtain
either an FPRAS or hardness of approximation result for the equivalent
problems $\mathsf{PHom_{\centernot L}}(\mathsf{1WP},\mathsf{Conn})$ and
$\mathsf{PHom_{\centernot L}}(\mathsf{DWT},\mathsf{Conn})$. It is also natural
to ask whether our results can be lifted from graph signatures to arbitrary
relational signatures, or whether they apply in the _unweighted_ setting where
all edges are required to have the same probability [6, 1, 23]. Another
question is whether we can classify the combined complexity of approximate PQE
for _disconnected_ queries, as was done in [7] in the case of exact
computation, for queries that feature disjunction such as UCQs (already in the
exact case [7]), or for more general query classes, e.g., with recursion [5].

## References

  * [1] Antoine Amarilli.  Uniform reliability for unbounded homomorphism-closed graph queries.  In ICDT, 2023.  doi:10.4230/LIPIcs.ICDT.2023.14.
  * [2] Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart.  Combined tractability of query evaluation via tree automata and cycluits.  In ICDT, 2017.  doi:10.4230/LIPIcs.ICDT.2017.6.
  * [3] Antoine Amarilli, Pierre Bourhis, and Pierre Senellart.  Provenance circuits for trees and treelike instances.  In ICALP, 2015.  doi:10.1007/978-3-662-47666-6_5.
  * [4] Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart.  Connecting knowledge compilation classes and width parameters.  ToCS, 2020\.  doi:10.1007/s00224-019-09930-2.
  * [5] Antoine Amarilli and İsmail İlkan Ceylan.  The dichotomy of evaluating homomorphism-closed queries on probabilistic graphs.  LMCS, 2022.  doi:10.46298/lmcs-18(1:2)2022.
  * [6] Antoine Amarilli and Benny Kimelfeld.  Uniform reliability of self-join-free conjunctive queries.  LMCS, 2022.  doi:10.46298/lmcs-18(4:3)2022.
  * [7] Antoine Amarilli, Mikaël Monet, and Pierre Senellart.  Conjunctive queries on probabilistic graphs: Combined complexity.  In PODS, 2017.  doi:10.1145/3034786.3056121.
  * [8] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros.  #NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes.  J. ACM, 68(6), 2021.  Extended version available as arXiv preprint arXiv:1906.09226 [cs.DS].  doi:10.1145/3477045.
  * [9] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros.  When is approximate counting for conjunctive queries tractable?  In STOC. ACM, 2021.  Extended version available as arXiv preprint arXiv:2005.10029 [cs.DS].  doi:10.1145/3406325.3451014.
  * [10] Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu.  Exact model counting of query expressions: Limitations of propositional methods.  TODS, 42(1), 2017.
  * [11] Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdrzálek.  The DAG-width of directed graphs.  J. Comb. Theory, Ser. B, 102(4), 2012.  doi:10.1016/j.jctb.2012.04.004.
  * [12] Robert M. Corless, Gaston H. Gonnet, D. E. G. Hare, David J. Jeffrey, and Donald E. Knuth.  On the Lambert _W_ function.  Adv. Comput. Math., 5(1), 1996.  doi:10.1007/BF02124750.
  * [13] Nilesh N. Dalvi and Dan Suciu.  Efficient query evaluation on probabilistic databases.  In VLDB, 2004.  doi:10.1016/B978-012088469-8.50076-0.
  * [14] Nilesh N. Dalvi and Dan Suciu.  The dichotomy of probabilistic inference for unions of conjunctive queries.  J. ACM, 59(6), 2012.  doi:10.1145/2395116.2395119.
  * [15] Adnan Darwiche.  Decomposable negation normal form.  J. ACM, 48(4), 2001.  doi:10.1145/502090.502091.
  * [16] Adnan Darwiche and Pierre Marquis.  A knowledge compilation map.  J. Artif. Intell. Res., 17, 2002.  doi:10.1613/jair.989.
  * [17] Martin Grohe and Dániel Marx.  On tree width, bramble size, and expansion.  J. Comb. Theory, Ser. B, 99(1), 2009.  doi:10.1016/j.jctb.2008.06.004.
  * [18] Heng Guo and Mark Jerrum.  A polynomial-time approximation algorithm for all-terminal network reliability.  SIAM J. Comput., 48(3), 2019.  doi:10.1137/18M1201846.
  * [19] Tomasz Imielinski and Witold Lipski Jr.  Incomplete information in relational databases.  J. ACM, 31(4), 1984.  doi:10.1145/1634.1886.
  * [20] Abhay Kumar Jha and Dan Suciu.  Knowledge compilation meets database theory: Compiling queries to decision diagrams.  ToCS, 52(3), 2013.  doi:10.1007/s00224-012-9392-5.
  * [21] Ravi Kannan.  Markov chains and polynomial time algorithms.  In FOCS. IEEE, 1994.  doi:10.1109/SFCS.1994.365726.
  * [22] David R. Karger.  A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem.  SIAM Rev., 43(3), 2001.  doi:10.1137/S0036144501387141.
  * [23] Batya Kenig and Dan Suciu.  A dichotomy for the generalized model counting problem for unions of conjunctive queries.  In PODS, 2021.  doi:10.1145/3452021.3458313.
  * [24] Jingcheng Liu and Pinyan Lu.  FPTAS for counting monotone CNF.  In SODA. SIAM, 2015.  doi:10.1137/1.9781611973730.101.
  * [25] Mikaël Monet.  Combined complexity of probabilistic query evaluation. (Complexité combinée d’évaluation de requêtes sur des données probabilistes).  PhD thesis, University of Paris-Saclay, France, 2018.  https://pastel.archives-ouvertes.fr/tel-01980366.
  * [26] Mikaël Monet.  Solving a special case of the intensional vs extensional conjecture in probabilistic databases.  In PODS. ACM, 2020.  doi:10.1145/3375395.3387642.
  * [27] Knot Pipatsrisawat and Adnan Darwiche.  New compilation languages based on structured decomposability.  In AAAI. AAAI Press, 2008.
  * [28] J. Scott Provan and Michael O. Ball.  The complexity of counting cuts and of computing the probability that a graph is connected.  SIAM J. Comput., 12(4), 1983.  doi:10.1137/0212053.
  * [29] Pierre Senellart.  Provenance in databases: Principles and applications.  In Reasoning Web, volume 11810 of LNCS. Springer, 2019.  doi:10.1007/978-3-030-31423-1_3.
  * [30] Allan Sly.  Computational transition at the uniqueness threshold.  In FOCS. IEEE Computer Society, 2010.  doi:10.1109/FOCS.2010.34.
  * [31] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch.  Probabilistic Databases.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.  ISBN: 978-1608456802.
  * [32] Leslie G. Valiant.  The complexity of enumeration and reliability problems.  SIAM J. Comput., 8(3), 1979.  doi:10.1137/0208032.
  * [33] Timothy van Bremen and Kuldeep S. Meel.  Probabilistic query evaluation: The combined FPRAS landscape.  In PODS. ACM, 2023.  doi:10.1145/3584372.3588677.
  * [34] Moshe Y. Vardi.  The complexity of relational query languages (extended abstract).  In STOC. ACM, 1982.  doi:10.1145/800070.802186.
  * [35] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In VLDB. IEEE Computer Society, 1981.
  * [36] Rico Zenklusen and Marco Laumanns.  High-confidence estimation of small _s_ -_t_ reliabilities in directed acyclic networks.  Networks, 57(4), 2011.  doi:10.1002/net.20412.

##  Appendix A Proof of Theorem 2.3

See 2.3

######  Proof A.1.

We may assume without loss of generality that $D$ contains no variable $v$
such that $w(v)=0$ or $w(v)=1$, since any such variable can be dealt with in
constant time by conditioning $D$ accordingly. We will use the fact that for
any positive integer $n$ and set of variables $S=\\{x_{1},\dots,x_{k}\\}$ such
that $k\geq\left\lceil{\log n}\right\rceil+1$, we can construct in time $O(k)$
a complete OBDD $C_{n}(x_{1},\dots,x_{k})$, implementing a “comparator” on the
variables of $S$, that tests if the integer represented by the binary string
$x_{1}\dots x_{k}$ is strictly less than $n$ (hence,
$C_{n}(x_{1},\dots,x_{k})$ has precisely $n$ satisfying assignments, for any
permitted value of $k$).

By [4, Lemma 3.16], we may assume that $D$ is complete; thus, there is a
bijection between the models of the Boolean function captured by $D$, and the
paths from the root to the 1-sink of $D$. Now, complete the following
procedure for every variable label $v_{i}$ with weight $w(v_{i})=p_{i}/q_{i}$
appearing in $D$. Set $k=\left\lceil{\log d}\right\rceil+1$, where
$d=\max\\{p_{i},q_{i}-p_{i}\\}$. Send the $1$-edge emanating from every node
$r\in D$ labelled with $v_{i}$ to the OBDD $C_{p_{i}}(x_{1},\dots,x_{k})$
(where $x_{1},\dots,x_{k}$ are fresh variables), redirecting edges to the
$1$-sink of $C_{p}(x_{1},\dots,x_{k})$ to the original destination of the
$1$-edge from $n$. Do the same for $0$-edge from $r$, but with the OBDD
$C_{q_{i}-p_{i}}(x_{1},\dots,x_{k})$. Observe that $D$ remains a complete
nOBDD. Moreover, it is not difficult to see that there are now exactly $p_{i}$
paths from the root to the 1-sink of $D$ that pass through the $1$-edge
emanating from $r$, and $q_{i}-p_{i}$ paths passing through the $0$-edge.

After repeating this process for every variable in $D$, we may apply Theorem
2.2, before normalizing the result by the product of the weight denominators
$\prod q_{i}$.

##  Appendix B Proof of Lemma 3.8

See 3.8

######  Proof B.1.

Let $G$ be a $\mathsf{DWT}$ query. We build $G^{\prime}$ following a tree
traversal of $G$. More precisely, we define the translation inductively as
follows. If $G$ is the trivial query with no edges, then we let the
translation of $G$ be the trivial query with no edges. Otherwise, let $x$ be
the root of $G$, let
$x\xrightarrow{R_{1}}y_{1},\ldots,x\xrightarrow{R_{n}}y_{n}$ be the successive
children, and call $G_{1},\ldots,G_{n}$ the $\mathsf{DWT}$ subqueries of $G$
respectively rooted at $y_{1},\ldots,y_{n}$. We define the translation of $G$
to be
$\xrightarrow{R_{1}}G^{\prime}_{1}\xleftarrow{R_{1}}\cdots\xrightarrow{R_{n}}G^{\prime}_{n}\xleftarrow{R_{n}}$,
where $G_{1}^{\prime},\ldots,G_{n}^{\prime}$ are the respective translations
of $G_{1}$, …, $G_{n}$. This translation is in linear time, and the translated
query has twice as many edges as the original query. Note that we can also
inductively define a homomorphism from $G^{\prime}$ to $G$ mapping the first
and last elements of $G^{\prime}$ to the root of $G$: this is immediate in the
base case, and in the inductive claim we obtain suitable homomorphisms from
each $G_{i}^{\prime}$ to each $G_{i}$ by induction and combine them in the
expected way.

We claim that, on any $\mathsf{DWT}$ instance $H$, there is a match of $G$
mapping the root to $a$ iff there is a match of $G^{\prime}$ mapping both the
first variable and last variable of the path to $a$. One direction is clear:
from the homomorphism presented earlier that maps $G^{\prime}$ to $G$, we know
that any match of $G$ in $H$ implies that there is a match of $G^{\prime}$ in
$H$ mapping the first and last elements as prescribed. Let us show the
converse, and let us actually show by induction on $G$ a stronger claim: if
there is a match of $G^{\prime}$ mapping the first variable of $G^{\prime}$ to
a vertex $a$, then the last variable is also mapped to $a$ and there is a
match of $G$ mapping the root variable to $a$. If $G$ is the vacuous query,
then this is immediate: a match of the empty query $G^{\prime}$ mapping the
first variable to $a$ must also map the last variable to $a$ (it is the same
variable), and we conclude. Otherwise, let us write $x$ the root of $G$ and
$x\xrightarrow{R_{1}}y_{1},\ldots,x\xrightarrow{R_{n}}y_{n}$ be the children
and $G_{1},\ldots,G_{n}$ the subqueries as above. We know that the match of
$G^{\prime}$ maps the first variable to a vertex $a$, and as $H$ is a
$\mathsf{DWT}$ instance it maps $x$ to a child $a_{1}$ of $a$. Considering
$G_{1}$ and its translation $G^{\prime}_{1}$, we notice that we have a match
of $G_{1}^{\prime}$ where the first variable is mapped to $a_{1}$. Hence, by
induction, the last variable is also mapped to $a_{1}$, and we have a match of
$G_{1}$ where the root variable is mapped to $a_{1}$. Now, as $H$ is a
$\mathsf{DWT}$ instance, the next edge $\xleftarrow{R_{1}}$ must be mapped to
the edge connecting $a$ and $a_{1}$, so that the next variable in $G^{\prime}$
is mapped to $a$. Repeating this argument for the successive child edges and
child queries in $G$, we conclude that the last variable of $G^{\prime}$ is
mapped to $a$, and we obtain matches of $G_{1},\ldots,G_{n}$ that can be
combined to a match of $G$.

##  Appendix C Proof of Proposition 4.1

See 4.1

######  Proof C.1.

Consider the following reduction from the $\\#\mathsf{P}$-hard problem
$\sharp\textsc{BIS}$, which asks to count the independent sets of a bipartite
undirected graph $B=(X,Y,E_{G})$. We reduce to $\mathsf{PHom_{\centernot
L}}(G,\mathsf{DAG})$, where $G$ is fixed to be the $\mathsf{1WP}$ of length
three, i.e., $\rightarrow\rightarrow\rightarrow$.

Construct a probabilistic graph $H=(\\{s,t\\}\sqcup X\sqcup Y,E_{H})$ and
probability labelling $\pi$, where $s$ and $t$ are fresh vertices, and the
edge set $E_{H}$ comprises:

  * •

a directed edge $s\rightarrow a$ for every $a\in X$, with probability $0.5$;

  * •

a directed edge $a\rightarrow b$ for every $(a,b)\in E_{G}$, with probability
$1$ (i.e., the original bipartite graph instance, with every edge directed
from $X$ towards $Y$);

  * •

a directed edge $b\rightarrow s$ for every $b\in Y$, with probability $0.5$.

We claim that $\Pr_{\pi}(G\rightsquigarrow H)$ is precisely the number of
independent sets of $B$, divided by $|X\sqcup Y|$. Indeed, just consider the
natural bijection between the subgraphs of $H$ and the independent sets of
$B$, where for $a\in X$ we keep the edge $s\rightarrow a$ iff $a$ is in the
independent set, and for $b\in Y$ the edge $b\rightarrow s$ iff $b$ is in the
independent set.

##  Appendix D Proof of Proposition 4.2

See 4.2

######  Proof D.1.

Let $G$ be a $\mathsf{DWT}$ query graph, and $m$ its height, i.e., the length
of the longest directed path it contains. Let $G^{\prime}$ be this
$\mathsf{1WP}$ of length $m$, computable in polynomial time from $G$. We claim
the following.

######  Claim 5.

For any $H\in\mathsf{DAG}$, $\mathsf{PHom_{\centernot
L}}(G,H)=\mathsf{PHom_{\centernot L}}(G^{\prime},H)$.

Certainly, if $H^{\prime}\subseteq H$ admits a homomorphism from $G$, then it
admits one from $G^{\prime}$ too since $G^{\prime}\subseteq G$. On the other
hand, if $H^{\prime}$ admits a homomorphism from $G^{\prime}$, then it also
admits one from $G$: just map all vertices of distance $i$ from the root of
$G$ to the image of the $i$-th vertex of $G^{\prime}$. Now the result follows
from the FPRAS for $\mathsf{PHom_{\centernot L}}(G^{\prime},\mathsf{DAG})$
given by Proposition 3.1.