Antoine Amarilli Ltci

Mikaël Monet

Pierre Senellart

Conjunctive Queries on Probabilistic Graphs: Combined Complexity

 have been proposed to lower the complexity, these known tractable cases usually do not apply to combined complexity, i.e., when the query is not fixed. This leaves open the question of which query and instance languages ensure the tractability of probabilistic query evaluation in combined complexity.

, the X-property for tractable CSP from [25], graded DAGs [28] and various coding techniques for hardness proofs.

INTRODUCTION

Uncertainty naturally arises in many data management applications, when integrating data that may be untrustworthy, erroneous, or outdated; or when generating or annotating data using information extraction or machine learning approaches. The framework of probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF] has been introduced to answer such needs: it provides a natural semantics for concise representations of probability distributions on data, and allows the user to evaluate queries directly on the representations. The simplest probabilistic framework is that of tuple-independent databases (TID), where each tuple in the relational database is annotated with a probability of actually being present, assuming independence across all tuples. Evaluating a Boolean query Q over a TID instance I means computing the probability that Q is true according to the distribution of I, or in other words, the total probability mass of the possible worlds of I that satisfy Q.

As is usual in database theory, the complexity of this probabilistic query evaluation problem (PQE) can be measured as a function of both I and Q, namely, combined complexity [START_REF] Vardi | On the complexity of bounded-variable queries[END_REF], or as a function of I when the query Q is fixed, called data complexity. Almost all works on PQE so far have focused on data complexity, where they have explored the general intractability of PQE in this sense. Indeed, while non-probabilistic query evaluation of fixed queries in firstorder logic has polynomial-time data complexity (specifically, AC 0 ), the PQE problem is #P-hard1 already for some fixed conjunctive queries [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF]. Specifically, the celebrated PQE result by Dalvi and Suciu [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], has shown a dichotomy on unions of conjunctive queries: some are safe queries, enjoying PTIME data complexity (specifically, linear [START_REF] Ceylan | Open-world probabilistic databases[END_REF]), and all other queries are #P-hard. Earlier work by some of the present authors has shown also a dichotomy on instance families for fixed monadic second-order queries, with tractable data complexity for bounded-treewidth families [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF], and intractability otherwise under some assumptions [START_REF] Amarilli | Tractable lineages on treelike instances: Limits and extensions[END_REF].

However, even when PQE is tractable in data complexity, the task may still be infeasible because of unrealistically large constants that depend on the query. For instance, our approach in [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF] is nonelementary in the query, and the algorithm for safe queries in [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] is generally super-exponential in the query [START_REF] Suciu | Probabilistic Databases[END_REF]. For this reason, we believe that it is also important to achieve a good understanding of the combined complexity of PQE, and to isolate cases where PQE is tractable in combined complexity; similarly to how, e.g., Yannakakis' algorithm can evaluate α-acyclic queries on non-probabilistic instances with tractable combined complexity [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]. This motivates the question studied in this paper: for which classes of queries and instances does PQE enjoy tractable combined complexity? Related work. Surprisingly, the question of achieving combined tractability for PQE does not seem to have been studied before. To our knowledge, the only exception is in the setting of probabilistic XML [START_REF] Kimelfeld | Probabilistic XML: models and complexity[END_REF], where deterministic tree automata queries were shown to enjoy tractable combined complexity [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF]. In the context of relational databases, our recent work [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits[END_REF] shows the combined tractability of provenance computation for a specific Datalog fragment on boundedtreewidth instances, but observes that these results do not seem to give tractability of PQE, which is already intractable in much more restricted settings. These results, however (Propositions 36 and 38 of [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]), do not give a complete picture of the combined complexity of PQE; in particular, they do not even give any non-trivial setting where it is tractable.

Questions of combined tractability have also been studied in the setting of constraint satisfaction problems (CSP), following a well-known connection between CSP and the conjunctive query evaluation problem in database theory, or the study of the graph homomorphism problem (see, e.g., [START_REF] Grohe | The complexity of homomorphism and constraint satisfaction problems seen from the other side[END_REF]). We can then see the restriction of PQE to conjunctive queries as a probabilistic, or weighted, variant of these problems, but we are not aware of any existing study of this variant. In the graph homomorphism setting, a related but different problem is that of counting graph homomorphisms [START_REF] Bulatov | The complexity of the counting constraint satisfaction problem[END_REF]: but this amounts to counting the number of matches of a query in a database instance, which is different from counting the possible worlds of an instance where the query has some match, as we do. A more related problem is #SUB [START_REF] Curticapean | Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts[END_REF], which asks, given a query graph G and an instance graph H, for the number of subgraphs of H which are isomorphic to G. When all facts are labeled with 1/2, our problem asks instead for the number of subgraphs of H to which G admits a homomorphism. A further difference is that we allow arbitrary probability annotations, amounting to a form of weighted counting; in particular, facts can be given probability 1.

Problem statement. Inspired by the connection to graph homomorphism and CSP, in this paper we investigate the probabilistic query evaluation problem for conjunctive queries on tuple-independent instances, over arity-two signatures. To our knowledge, our paper is the first to focus on the combined complexity of conjunctive query evaluation on probabilistic relational data. For simplicity of exposition, we will phrase our problem in terms of graphs: given a query graph and a probabilistic instance graph, where each edge is annotated by a probability, we must determine the probability that the query graph has a homomorphism to the instance graph, i.e., the total probability mass of the subgraphs which ensure this, assuming independence between edges. We always assume the query and instance graphs to be directed.

As we will see, the problem is generally intractable, so we will have to study restricted settings. We accordingly study this problem under assumptions on the query and input graphs. Inspired by our prior intractability results [START_REF] Amarilli | Tractable lineages on treelike instances: Limits and extensions[END_REF], one general assumption that we will make is to impose treelikeness of the instance. In fact, we will generally restrict it to be a polytree, i.e., a directed graph whose underlying undirected graph is a tree. As we will see, however, even this restriction does not suffice to ensure tractability, so we study the impact of several other features:

• Labels, i.e., whether edges of the query and instance can be labeled by a finite alphabet, as would be the case on a relational signature with more than one binary predicate. • Disconnectedness, i.e., allowing disconnected queries and instances. • Branching, i.e., allowing graphs to branch out, instead of requiring them to be a path.

• Two-wayness, i.e., allowing edges with arbitrary orientation, instead of requiring all edges to have the same orientation (as in a one-way path, or downward tree). We accordingly study our problem for labeled graphs and unlabeled graphs, and when query and instance graphs are in the following classes, that cover the possible combinations of the above characteristics: one-way and two-way paths, downward trees and polytrees, and disjoint unions thereof.

Results. This paper presents our combined complexity re- sults for the probabilistic query evaluation problem in all these settings. After introducing the preliminaries and defining the problem in Section 2, we first study the impact of disconnectedness in instances and queries in Section 3. While we can easily show that disconnectedness does not matter for instances (Lemma 3.7), we show that disconnectedness of queries has an unexpected impact on complexity: in the labeled case, even the simplest disconnected queries on the simplest kinds of instances are intractable (Proposition 3.3): this result is shown via the hardness of counting edge covers in bipartite graphs. The picture for disconnected queries is more complex in the unlabeled case (see Table 1): indeed, the problem is still hard when allowing two-wayness in the query and instance (as it can be used to simulate labels, see Proposition 3.4), but disallowing two-wayness in the instance ensure tractability of all queries. This latter result (Proposition 3.6) is established by showing that all queries then essentially collapse to a one-way path: we do so by assigning a level to all vertices of the query using a notion of graded DAGs [START_REF] Odagiri | On the greatest number of paths and maximal paths for a class of directed acyclic graphs[END_REF][START_REF] Schröder | Ordered Sets[END_REF].

We then focus on connected queries, and first study the labeled setting in Section 4; see Table 2 for a summary of results. We show that disallowing instance branching ensures the tractability of all connected queries (Proposition 4.11), and that disallowing branching in the query and two-wayness in the instance and query also does (Proposition 4.10). These two results are shown by computing a Boolean lineage of the query [START_REF] Suciu | Probabilistic Databases[END_REF], and proving that we can tractably evaluate its probability because it is β-acyclic [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF], thanks to the restricted instance structure. For the first result, this process further relies on a CSP tool to show the tractability of homomorphism testing in labeled two-way paths, a condition dubbed the X-property [START_REF] Gutjahr | Polynomial graph-colorings[END_REF][START_REF] Gottlob | Conjunctive queries over trees[END_REF]. We show the intractability of all other cases (Propositions 4.1, 4.4, and 4.5), by coding #SAT-reduction, reusing in part a coding from [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF].

We last study the unlabeled setting for connected queries in Section 5. We show that disallowing query branching and two-wayness suffices to obtain tractability, provided that the instance is a polytree (Proposition 5.4): this result is proven by building in PTIME a deterministic tree automaton to test the length of the longest path, and compiling a d-DNNF lineage as in [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF]. This result immediately extends to branching queries, as they are equivalent to paths in this case (Proposition 5.5). We complete the picture by showing that, by contrast, allowing two-wayness in the query leads to intractability on polytrees, by a variant of our coding technique (Proposition 5.6). We then conclude in Section 6.

Our results completely classify the complexity of probabilistic conjunctive query evaluation for all combinations of instance and query restrictions, in the labeled and unlabeled setting. Full proofs are given in appendix.

PRELIMINARIES

We first provide some formal definitions of the concepts we use in this paper, and introduce the probabilistic graph homomorphism problem and the different classes of graphs that we consider.

Graphs and homomorphisms.

Let σ be a finite non-empty set of labels. When |σ| > 1, we say that we are in the labeled setting; when |σ| = 1, in the unlabeled setting.

We consider directed graphs with edge labels from σ, i.e., triples H = (V, E, λ) with V a non-empty finite set of vertices, E ⊆ V 2 a set of edges, and λ : E → σ a labeling function. We write a R -→ b for an edge e = (a, b) with label λ(e) = R. Note that we do not allow multi-edges: an edge e has a unique label λ(e). When |σ| = 1, i.e., in the unlabeled setting, we simply write (V, E) for the graph and a → b for an edge. Unless otherwise specified, all graphs that we consider in this paper are directed.

A graph H = (V , E , λ ) is a subgraph of the graph H = (V, E, λ), written H ⊆ H, when we have V = V , E ⊆ E, and when λ is λ |E , i.e., the restriction of λ to E . (Note that, in a slightly non-standard way, we impose that subgraphs have the same set of vertices than the original graph; this will simplify some notation.)

A graph homomorphism h from some graph G = (VG, EG, λG)

to some graph H = (VH , EH , λH ) is a function h : VG → VH such that, for all (u, v) ∈ EG, we have (h(u), h(v)) ∈ EH and further λH ((h(u), h(v))) = λG((u, v)). A match of G in H is the image in H of
such a homomorphism h, i.e., the graph with vertices h(u) for u ∈ VG and edges (h(u), h(v))) for (u, v) ∈ EG. Note that two different homomorphisms may define the same match. Also note that two distinct nodes of G could have the same image by h, so a match of G in H is not necessarily homomorphic to G. We write G ; H when there exists a homomorphism from G to H. We call two graphs G and G equivalent if, for any graph H, we have G ; H iff G ; H. It is easily seen that G and G are equivalent if and only if G ; G and G ; G.

Probabilistic graphs. A probability distribution on graphs is a function Pr from a finite set W of graphs (called the possible worlds of Pr) to values in [0; 1] represented as rational numbers, such that the probabilities of all possible worlds sum to 1, namely, H∈W Pr(H) = 1.

A probabilistic graph is intuitively a concise representation of a probability distribution. Formally, it is a pair (H, π) where H is a graph with edge labels from σ and where π is a probability function π : E → [0; 1] that maps every edge e of H to a probability π(e), represented as a rational number. Note that each edge (u, v) in a probabilistic graph (H, π) is annotated both with a label λ((u, v)) ∈ σ, and a probability π((u, v)).

The probability distribution Pr defined by the probabilistic graph (H, π) is obtained intuitively by considering that edges are kept or deleted independently according to the indicated probability. Formally, the possible worlds W of Pr are the subgraphs of H = (V, E, λ), and for H = (V, E , λ |E ) ⊆ H we define Pr(H ) • • = e∈E π(e) × e∈E\E (1 -π(e)). Note that, when H has edges labeled with 0 or 1, some possible worlds are given probability 0 by π.

Example 2.1. Figure 1 represents a probabilistic graph (H, π) on signature σ = {R, S}, where each edge is annotated The possible world where all R-edges are kept and all Sedges are removed has probability 0.1 × 1 × 0.8 × 0.1 × 0.05 × (1 -0.7).

H: • • • • 1 R 0.1 R R 0.1 R 0.05 S 0.7 R 0.8
Probabilistic graph homomorphism. The goal of this paper is to study the probabilistic homomorphism problem PHom, for the set of labels σ that we fixed: given a graph G on σ and a probabilistic graph (H, π) on σ, compute the probability that there exists a homomorphism from G to H under Pr, i.e., the sum of the probabilities of all subgraphs of H to which G has a homomorphism: Following database terminology, we call G the query graph and (H, π) the (probabilistic) instance graph. Indeed, the PHom problem is easily seen to be equivalent to conjunctive query evaluation on probabilistic tuple-independent relational databases [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF], over binary relational signatures.

Pr(G ; H) • • = H ⊆H G;H Pr(H ).
Note that, in this paper, we measure the complexity of PHom as a function of both the query graph G and of the instance graph (H, π), i.e., in database terminology, we measure the combined complexity [START_REF] Vardi | On the complexity of bounded-variable queries[END_REF] of probabilistic query evaluation. The PHom problem is known to be #P-hard in general [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF] (even for some fixed query graphs): by this, we mean that it is hard (under polynomial-time reductions) for the class #P of counting problems that can be expressed as the number of accepting paths of a nondeterministic polynomialtime Turing machine. To achieve tractable complexity for PHom, we will classify the complexity of PHom under various restrictions. We say that the complexity of some variant of the problem is tractable if the probability can be computed by a deterministic polynomial-time Turing machine: by a slight abuse of terminology, we then say that it is in PTIME.

All PHom variants that we study will be shown either to be PTIME in this sense, or to be #P-hard.

We will study restrictions of PHom first by distinguishing the labeled and unlabeled settings. We write PHom L for the problem when the fixed label set σ is such that |σ| > 1, and PHom L when the fixed σ is such that |σ| = 1. The second restriction concerns the input query graphs and instance graphs. We will model restrictions on these graphs by requiring them to be taken from specific graph classes, where by graph class we simply mean an infinite set of graphs. Inspired by the notation used in CSP, for two classes G and H of graphs in the labeled setting, we denote PHom L (G, H) the problem that takes as input a graph G in class G and a probabilistic graph (H, π) with H in class H, and computes the probability Pr(G ; H). We denote the same problem in the unlabeled setting by PHom L (G, H).

Graph classes.

The graph classes which we study in this paper are defined as follows, on a graph G with edge labels from σ:

• G is a one-way path (1WP) if it is of the form a1 R 1 --→ • • • R m-1
----→ am for some m, with all a1, . . . , am being pairwise distinct, and with Ri ∈ σ for 1 i < m.

• G is a two-way path (2WP) if it is of the form a1 -• • • -am, with all a1, . . . , am being pairwise distinct, and each -being

R i --→ or R i ← --(but not both) for some label Ri ∈ σ.
• G is a downwards tree (DWT) if it is a rooted unranked tree (each node can have an arbitrary number of children), with all edges going from parent to child in the tree. • G is a polytree (PT) if its underlying undirected graph is an unranked tree, without restriction on edge directions.

We also consider the class Connected of connected graphs, and write All the class of all graphs. The inclusion diagram between our graph classes is shown in Figure 2. See Figure 3 for an example of a labeled one-way path and two-way path, and Figure 4 for an unlabeled downwards tree and polytree. We also introduce the classes 1WP (resp., 2WP, DWT, PT) of graphs that are disjoint unions of 1WP (resp., 2WP, DWT, PT), that is, of possibly disconnected graphs whose connected components are 1WP (resp., 2WP, DWT, PT).

Our graph classes were chosen to be representative of different features of graphs that will have an impact in the complexity of the PHom problem, namely, labeling, twowayness, branching, and disconnectedness. Indeed, 2WP (resp., PT) adds two-wayness to 1WP (resp., DWT); DWT (resp., PT) adds branching to 1WP (resp., 2WP); and 1WP (resp., 2WP, DWT, PT) adds disconnectedness to 1WP (resp., 2WP, DWT, PT). In the following sections, we investigate the complexity of probabilistic graph homomorphism for these various classes of conjunctive queries and instances.

DISCONNECTED CASE

We first consider the case where either the query or probabilistic instance graph is disconnected, i.e., not in the Connected class. When the query is disconnected, we show in this section that the probabilistic homomorphism problem is #P-hard in all but the most restricted of cases (in particular in the labeled setting), which justifies that we restrict to connected queries in the rest of the paper. On the other hand, we will show that disconnectedness in the probabilistic instance graph has essentially no impact on combined complexity.

Labeled Disconnected Queries

We establish our main intractability result on disconnected queries by reduction from the #Bipartite-Edge-Cover problem on undirected graphs: Definition 3.1. An undirected graph is bipartite if its vertices can be partitioned into two classes such that no edge connects two vertices of the same class. An edge cover of an undirected graph is a subset of its edges such that every vertex is incident to at least one edge of the subset. #Bipartite-Edge-Cover is the problem, given a bipartite undirected graph, of counting its number of edge covers.

This problem was shown in [START_REF] Khanna | Queries with difference on probabilistic databases[END_REF] to be intractable. The result can also be proven using Valiant's holographic reductions [START_REF] Valiant | Holographic algorithms[END_REF] and the results of Cai, Lu, and Xia [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF], as explained in [START_REF] Williams | Complexity of counting the number of edge covers of a graph[END_REF]: see Appendix D. Theorem 3.2. [START_REF] Khanna | Queries with difference on probabilistic databases[END_REF][START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF][START_REF] Williams | Complexity of counting the number of edge covers of a graph[END_REF] The #Bipartite-Edge-Cover problem is #P-complete.

We can then use this result to show intractability for the simplest forms of disconnected query graphs ( 1WP) on the simplest forms of probabilistic instance graphs (1WP), in the labeled case:

Proposition 3.3. PHom L ( 1WP, 1WP) is #P-hard.
Proof. We reduce from #Bipartite-Edge-Cover. Let Γ = (X Y, E) be an input to #Bipartite-Edge-Cover, i.e., a bipartite undirected graph with parts X and Y ; we write X = (x1, . . . , xn l ), Y = (y1, . . . , yn r ), E = (e1, . . . , em), and for all 1 i m we write ei = (x l i , yr i ), with 1 li n l and 1 ri nr.

We first construct in PTIME the 1WP probabilistic graph (H, π): see Figure 5 for an illustration of the construction. Specifically, for 1 j m, we construct the following 1WP:

Γ = (X Y, E): x1 x2 y1 y2 y3 e1 e2 e3 e4 G: C L V (x1) C L L V (x2) V R C (y1) V R R C (y2) V R R R C (y3) H: C L V (e1) R C L V (e2) R R C L V (e3) R R R C L L V (e4) R C
He j • • = ( L -→) l j V -→ ( R -→) r j .
The graph H is then defined as:

C -→ He 1 C -→ He 2 C -→ • • • C -→ He m C -→ .
We define π as follows: edges labeled by V have probability 1

2

(intuitively coding whether an edge is part of the candidate cover), all others have probability 1.

We then construct the query graph G ∈ 1WP, coding the edge covering constraints. For every 1

i n l , the graph G contains the 1WP component C -→ ( L -→) i V
-→, and for every 1 i nr, the graph G contains the 1WP component

V -→ ( R -→) i C -→. It is clear that H is in 1WP, G is in 1WP
and that both can be constructed in PTIME from Γ. We now show that Pr(G ; H) is exactly the number of edge covers of Γ divided by 2 m , so that the computation of the latter reduces in PTIME to the computation of the former, concluding the proof.

To see why, we define a bijection between the subsets of edges of Γ, seen as valuations ν : E → {0, 1}, to the possible worlds H of H of non-zero probability. We do so in the expected way: keep the one V -edge V -→ of He i iff ν(ei) = 1. We now show that there is a homomorphism from G to H if and only if ν is an edge cover of Γ. As the number of H 's such that there is a homomorphism from G to H is exactly Pr(G ; H) × 2 m , this will allow us to conclude.

Indeed, if there is a homomorphism h from G to H , then, considering the 1WP component in G that codes the constraint on xi (resp., on yi), its image must be of the form

C -→ ( L -→) i V -→ (resp., V -→ ( R -→) i C -→
), but then by construction of H the V -fact must correspond to an edge e such that xi (resp., yi) is adjacent to e, so that we have ν(e) = 1 and so xi (resp., yi) is covered. As this is true for each 1WP component, all the vertices are covered and ν is indeed an edge cover of Γ.

Conversely, suppose that ν is an edge cover of Γ, then for every vertex xi (resp., yi) we know that there exists 1 j m such that ν(ej) = 1 and lj = i (resp., rj = i), and we can use the V -fact corresponding to ej and the surrounding facts to build the homomorphism as above from each component of G to H . The proof of Proposition 3.3 crucially requires multiple labels in the signature. Indeed, it is easy to see that, in the unlabeled setting, a query graph in 1WP (or even in DWT) is equivalent to the longest path within the graph, and we will show further (Proposition 5.5) that PHom L (1WP, 1WP) (indeed, even PHom L ( DWT, PT)) is PTIME.

Unlabeled Disconnected Queries

In light of this intractability result, let us now consider the unlabeled setting. We show in Table 1 where the tractability frontier lies. First, introducing two-wayness in both query and instance graphs is enough to obtain an analogue of the intractability of Proposition 3.3:

Proposition 3.4. PHom L ( 2WP, 2WP) is #P-hard.
Proof. We reduce, again, from the #P-hard problem #Bipartite-Edge-Cover. The idea of the reduction is similar to that used in the proof of Proposition 3.3, but we face the additional difficulty of not being allowed to use labels. Fortunately, we can use two-wayness to simulate them.

Let Γ = (X Y, E) be an input of #Bipartite-Edge-Cover. Consider the reduction from Γ used in the proof of Proposition 3.3 and the 1WP probabilistic graph (H, π) and the 1WP query graph G that were constructed. We construct from H and G the unlabeled probabilistic graph H and unlabeled 2WP query graph G as follows:

• replace each L-or R-labeled edge a L -→ b or a R -→ b in H and G by 3 edges a →→← b; • replace each C-labeled edge a C -→ b of H and G by 3 edges a ←←← b; • replace each V -labeled edge a V -→ b of H and G by 6 edges a →→→→→← b.
All edges of H have probability 1, except the first edge of each sequence of 6 edges that replaced a V -labeled edge, which has probability 1 2 . Consider a 1WP component of G that codes the constraint on a vertex from Y , e.g

V -→ ( R -→) i C
-→, which was rewritten in G into →→→→→← (→→←) i ←←←. A homomorphism from this component into a possible world J of H must actually map to a rewriting of a

V -→ ( R -→) i C
-→ sequence in H : indeed, the key observation is that the first 5 → edges can only be matched to 5 consecutive → in J , which only exist as the first 5 edges of a sequence of 6 edges that replaced a V -labeled fact in H. There is no choice left to match the subsequent edges without failing. A similar observation holds for components coding the constraints on vertices from X (

C -→ ( L -→) i V -→).
Hence, we can show correctness of the reduction using the same argument as before.

Allowing two-wayness in both the query and the instance graphs thus allows us to simulate labels, so that PHom L is intractable. We will study in Section 5 what happens for query graph classes without two-wayness (i.e., 1WP, DWT, and unions thereof); so let us now consider the case of instance graph classes where two-wayness is forbidden, i.e., is in DWT. As we will show, PHom L of arbitrary query graphs on such DWT instance graphs is tractable. To this end, we need to introduce level mappings of acyclic directed graphs (DAGs):

Definition 3.5. A level mapping of a DAG G is a map- ping µ from the vertices of G to Z such that for each directed edge u → v of G we have µ(v) = µ(u) -1.
We call G a graded DAG if it has a level mapping.

An example of graded DAG together with a level mapping is given in Figure 6. It is easy to see (and shown in Proposition 1 of [START_REF] Odagiri | On the greatest number of paths and maximal paths for a class of directed acyclic graphs[END_REF]) that a DAG G is graded iff there are no two vertices u, v and two directed paths χ, χ in G from u to v such that χ and χ have different lengths (in the terminology of [START_REF] Odagiri | On the greatest number of paths and maximal paths for a class of directed acyclic graphs[END_REF], G does not have a jumping edge). Graded DAGs are related to the classical notion of graded ordered set [START_REF] Schröder | Ordered Sets[END_REF], and the level mapping function has been called in the literature a depth function [START_REF] Odagiri | On the greatest number of paths and maximal paths for a class of directed acyclic graphs[END_REF], a grading function [START_REF] Schröder | Ordered Sets[END_REF], a set of levels [START_REF] Schröder | Ordered Sets[END_REF], or a rank function [START_REF] Stanley | Enumerative Combinatorics[END_REF].

To obtain such a level mapping, we can proceed by picking one vertex in each connected component of G, mapping each of these vertices to level 0, and then exploring G by a breadth-first traversal and assigning the level of each vertex according to the level of the vertex used to reach it, visiting all edges and defining the image of each vertex. It is clear that this process yields a level mapping of G unless it tries to assign two different levels to the same vertex v, which cannot happen if there is no jumping edge [28, Proposition 1].

We will now use the notion of graded DAG to show:

Proposition 3.6. PHom L (All, DWT) is PTIME.
Proof sketch. We only give the idea when the query graph is connected and the graph instance H is a DWT (see Appendix for full proof). As we pointed out already, if the query graph G is not a graded DAG, then it has a cycle or a pair of vertices joined by two directed paths of different lengths: then, from the structure of the DWT instance graph, this clearly implies that Pr(G ; H) = 0. So it suffices to study the case when G is a graded DAG.

As we explained earlier, we can then compute in PTIME a level mapping µ of G. It is clear that, as G is connected, the level mapping µ is uniquely defined up to an additive constant. Hence, we shift µ so that the smallest value of its image is 0, and we then call the difference of levels of G the largest value m in the image of µ. Note that m is not the maximal length from a root of G to a leaf of G (see, e.g., Figure 6). We then claim that, on any possible world H of the DWT instance graph H, the query graph G is in fact equivalent to the 1WP query graph → m of length m. This allows us to conclude using Proposition 5.5.

One direction is easy to observe, because µ directly gives a homomorphism from G to → m . For the converse, suppose that a homomorphism h from G to H exists. Because G is connected and H is in DWT, the image of h is actually a DWT, call it T . Now it is easy to see that the image of a node that has level m -i in G has depth i in T , so that T (and so H ) contains the 1WP → m .

Disconnected Instances

We conclude our study of the disconnected case with the case of disconnected instance graphs, which we show to be less interesting than the disconnected query graphs that we studied so far. Specifically, when the query is connected, PHom on arbitrary instances can reduce in PTIME to PHom of the same queries on a corresponding class of connected instances: Lemma 3.7. For any class of graphs H, let H be the class of connected components of graphs in H. Then for any class of connected graphs G,

PHom L (G, H) reduces in PTIME to PHom L (G, H ), and PHom L (G, H) reduces in PTIME to PHom L (G, H ). Proof. Let G ∈ G, H ∈ H, and write H = H 1 . . . H n :
we have H i ∈ H for all 1 i n. Let π be a probability distribution over H: the independence assumption ensures that the edges of any H i are pairwise independent from those of any H j for i = j. Now, as G is connected, any image of a homomorphism from G to H must actually be included in some H i . Thus, the computation of Pr(G ; H) reduces to that of the Pr(G ; H i ) for 1 i n, as follows: We have thus completed our study of PHom L and PHom L for disconnected instances and/or disconnected queries, We accordingly focus on connected queries and instances in the next two sections.

Pr(G ; H) = 1 - 1 i n (1 -Pr(G ; H i )).

LABELED CONNECTED QUERIES

In this section, we focus on the labeled setting, i.e., the PHom L problem, for classes of connected queries and instances. Table 2 shows the entire classification of the labeled setting for the classes that we consider.

Intuitively, we show intractability for polytree instance graphs, and for downward trees instance graphs when the query graphs allow either two-wayness or branching. Conversely, we show tractability of one-way path query graphs on downward trees, and of arbitrary connected queries on two-way path instances. We first present the hardness results, and then the tractability results.

Hardness Results

We recall that, if we allow arbitrary connected unlabeled probabilistic instance graphs (or even just 4-partite graphs), then computing the probability that there exists a path of length 2 is already #P-hard: this is shown in [START_REF] Suciu | Probabilistic Databases[END_REF], and we will state this result in our context as Proposition 5.1 in the next section. Hence, if we want to obtain PTIME complexity for PHom, we need to restrict the class of instances. We can start by restricting the instances to be polytrees, but as we show, this does not suffice to ensure tractability:

Proposition 4.1. PHom L (1WP, PT) is #P-hard.
To show this result, we will reduce from the problem of computing the probability of a Boolean formula, which we now define: Definition 4.2. Given a set of variables X and a probability assignment π mapping each variable X in X to a rational probability π(X) ∈ [0, 1], we define the probability π(ν) of a valuation ν : X → {0, 1} as

π(ν) := X∈X , ν(X)=1 π(X) X∈X , ν(X)=0 (1 -π(X)) .
The Boolean probability computation problem is defined as follows: given a Boolean formula ϕ on variables X and a probability assignment π on X , compute the total probability of the valuations that satisfy ϕ, i.e., Pr(ϕ, π) = ν satisfies ϕ π(ν).

This problem is known to be #P-hard, even under severe restrictions on the formula ϕ. We will use the #PP2DNF formulation of the above problem, which is #P-hard [START_REF] Provan | The complexity of counting cuts and of computing the probability that a graph is connected[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF]:

Definition 4.3. A positive DNF is a Boolean formula ϕ of the form ϕ = 1 i m 1 j n i Xi,j , i.e.
, it is a disjunction of (conjunctive) clauses that are conjunctions of variables of X . We assume that each variable of X occurs in ϕ, as we can eliminate the others without loss of generality.

A positive partitioned 2-DNF (PP2DNF) is intuitively a positive DNF ϕ on a partitioned set of variables where each clause contains one variable from each partition. Formally, the variables of ϕ are X Y, where we write X = {X1, . . . , Xn 1 } and Y = {Y1, . . . , Yn 2 }, and ϕ is of the form j=1...m (Xx j ∧ Yy j ) with 1 xj n1 and 1 yj n2 for 1 j m.

The #PP2DNF problem is the Boolean probability computation problem when we impose that π maps every variable to 1/2, and that ϕ is a PP2DNF.

We show Proposition 4.1 by reducing from #PP2DNF: Proof sketch. The full proof is in appendix; see Figure 7 for an illustration. From the PP2DNF formula ϕ, we construct a PT probabilistic instance where each branch starting at the root describes a variable of the formula. The first edge is probabilistic and represents the choice of valuation. The edges are oriented upwards or downwards depending on whether the variable belongs to X or to Y. We add a special gadget at different depths of the branch to code the index of each of the clauses where the variable occurs.

We code satisfaction of the formula by a query that tests for a path of a specific length that starts and ends with the gadget. The query has a match exactly on possible worlds where we have set two variables to true such that the sum of the depths of the gadgets corresponds to the query length: this happens iff the two variables occur in the same clause.

Hence, restricting instances to polytrees is not sufficient to ensure tractability, even for 1WP query graphs. We must thus restrict the instance further, by disallowing one of the two remaining features, namely branching and two-wayness. The first option of disallowing branching, i.e., requiring the instance to be a 2WP, is studied in Section 4.2 below, where we show that the problem is tractable for arbitrary query graphs.

The second option is to forbid two-wayness on the instance, i.e., restrict it to be a DWT. In this case, we first show that intractability holds even when we also forbid two-wayness in the query graph, i.e., we also restrict it to be a DWT. The result follows from our earlier work on the combined complexity of query evaluation [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits[END_REF][START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]: Proposition 4.4 [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]. PHom L (DWT, DWT) is #P-hard.

H: R X1 X2 Y1 Y2 X1,3 X1,2 X1,1 X2,3 X2,2 X2,1 Y1,1 Y1,2 Y1,3 Y2,1 Y2,2 Y2,3 A1,1 A1,2 A2,3 B1,2 B2
If we forbid branching in the query graph instead of twowayness, requiring it to be a 2WP, then intractability still holds, which also follows from our earlier results: Proposition 4.5 [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]. PHom L (2WP, DWT) is #P-hard.

Thus, on DWT instances, the only remaining case is when the query is a one-way path. We will now show in the section below that this case is tractable, in addition to the case of arbitrary queries on 2WP instances that we left open above.

Tractability Results

The general proof technique to obtain PTIME combined complexity in this section is inspired by the probabilistic database literature [START_REF] Suciu | Probabilistic Databases[END_REF]: compute the lineage of G on H as a Boolean formula in positive disjunctive normal form (DNF), then compute its probability. Let us first define lineages: Definition 4.6. Let G be a query graph and (H, π) be a probabilistic graph with edge set E. For any valuation ν : E → {0, 1}, we denote by ν(H) the possible world of H where each edge e ∈ E is kept iff ν(e) = 1. Letting ϕ be a Boolean function whose variables are the edges of E, we say that ϕ captures the lineage of G on H if, for any valuation ν : E → {0, 1}, the function ϕ evaluates to 1 under ν iff we have G ; ν(H).

Lineage representations allow us to reduce the PHom problem to the Boolean probability computation problem on the lineage function (recall Definition 4.2). Formally, for any query graph G and probabilistic graph (H, π), given a Boolean function ϕ that captures the lineage of G on H, we compute the answer to PHom on G and (H, π) as the probability Pr(ϕ, π) of ϕ under π: it is immediate by definition that these two quantities are equal.

Of course, computing a lineage representation does not generally suffice to show tractability, because, as we explained earlier, the Boolean probability computation problem is generally intractable. However, computing a Boolean lineage allows us to leverage the known tractable classes of Boolean formulas. Specifically, we will show how to use the class of β-acyclic positive DNF formulas, which are known to be tractable [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF]. We define this notion, by first recalling the notion of a β-acyclic hypergraph, and then defining a β-acyclic positive DNF : [START_REF] Brault-Baron | Hypergraph acyclicity revisited[END_REF] if the set of hyperedges that contain it, i.e., {e ∈ E | v ∈ e}, is totally ordered by inclusion. In other words, we can write {e ∈ E | v ∈ e} as (e1, . . . , e k ) in a way that ensures that ei ⊆ ei+1 for all 1 i < k.

Definition 4.7. A hypergraph H = (V, E) is a finite set V of vertices and a set E of non-empty subsets of V , called hyperedges. For v ∈ V , we write H \ v for the hypergraph (V \ {v}, E ) where E is {e \ {v} | e ∈ E} \ {∅}. A vertex v ∈ V of H is called a β-leaf
A β-elimination order for a hypergraph H = (V, E) is defined inductively as follows:

• if E = ∅, then the empty tuple is a β-elimination order for H; • otherwise, a tuple (v1, . . . , vn) of vertices of H is a β-elimination order for H if v1 is a β-leaf in H and (v2, . . . , vn) is a β-elimination order for H \ v1.

The hypergraph H is β-acyclic if there is a β-elimination order for H.

We can see a positive DNF (recall Definition 4.3) as a hypergraph of clauses on the variables, and introduce the notion of β-acyclic positive DNFs accordingly: Definition 4.8. The hypergraph H(ϕ) of a positive DNF on variables X has X as vertex set and has one hyperedge per clause, i.e., we have H(ϕ) := (X , E) with E := {{Xi,j | 1 j ni} | 1 i m}. We say that the positive DNF ϕ is β-acyclic if H(ϕ) is β-acyclic.

It follows directly from results by Brault-Baron, Capelli, and Mengel about the β-acyclic #CSP d problem [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF] that we can tractably compute the probability of β-acyclic positive DNFs:

Theorem 4.9. The Boolean probability computation problem is in PTIME when restricted to β-acyclic positive DNF formulas.

Proof sketch. The #CSP d problem studied in [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF] is about computing a partition function over the hypergraph, under weighted constraints on hyperedges: it generalizes the problem of counting the number of valuations of β-acyclic formulae in conjunctive normal form (CNF) by [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF]Lemma 3]. We show how the result extends to β-acyclic positive DNF, using de Morgan's law, and to probability computation for weighted variables, using additional constraints on singleton variable sets.

We will then use the tractability of β-acyclic formulas to show PTIME combined complexity results for our PHom L problem. The first result that we show is tractability for labeled 1WP query graphs on DWT probabilistic instance graphs:2 Proposition 4.10. PHom L (1WP, DWT) is PTIME.

Proof sketch. Intuitively, the proof proceeds in three steps. The first step is to enumerate all candidate minimal matches of the query graph in the instance graph, i.e., subgraphs of the instance graph to which the query graph could have a homomorphism, and which are minimal for inclusion. As the query graph is a path, we know that the minimal matches are downward paths in the DWT instance: hence, as each vertex of the DWT instance can be the lowest vertex of at most one match, there are polynomially many matches to consider.

The second step is to decide which ones of these matches are actually a match of the query, by considering the labels: as both the query graph and the match are a 1WP, this is straightforward. These first two steps produce a positive DNF that captures the lineage of the query graph on the instance in the standard sense.

The third step is to notice that this lineage expression is β-acyclic: this is because its variables can be eliminated by considering the nodes of the instance DWT in a bottom-up fashion.

Interestingly, we were not able to prove this result using tree automata-based dynamic programming approach (like we will do later for Proposition 5.4).

The second result that we show is tractability when restricting the instance to be a 2WP, and allowing arbitrary connected queries (remember from Proposition 3.3 that the problem is hard even on 1WP instances if we allow disconnected queries): Proposition 4.11. PHom L (Connected, 2WP) is PTIME.

To show this result, we follow the same scheme as in the proof of Proposition 4.10 above: (i) enumerate all candidate matches; (ii) check whether they are indeed matches; and (iii) argue that the resulting lineage is β-acyclic. For the first step, there are polynomially many candidate matches to consider, because matches are necessarily connected subgraphs of the instance graph H, that are uniquely defined by their endpoints: this is where we use connectedness of the query. For the third step, the resulting lineage is β-acyclic for the same reason as in Proposition 4.10, as we can eliminate variables following the order of the path H: all connected subpaths containing an endpoint of the path are ordered by inclusion. What changes, however, is the second step: from the quadratically many possible matches, to compute the lineage expression, we must decide which ones are actually matches.

Deciding this for each subpath amounts to testing, given the connected query graph G and a candidate match H , whether G ; H , in the non-probabilistic sense. This graph homomorphism problem is generally intractable, but here the minimal match H is a 2WP (as it is a subpath of H), so it turns out to enjoy combined tractability. The corresponding result was first shown by Gutjahr [START_REF] Gutjahr | Polynomial graph-colorings[END_REF] for unlabeled graphs, when the instance graph is a path, or for more general instances satisfying a condition called the X-property; this was generalized to labeled graphs by Gottlob, Koch, and Schulz in [START_REF] Gottlob | Conjunctive queries over trees[END_REF]. We recall here the definition of this property: Definition 4.12 (Definition 3.2 of [START_REF] Gottlob | Conjunctive queries over trees[END_REF]). Let H = (V, E, λ) be a directed graph with labels on σ, let R ∈ σ, and let < be a total order on V . Then R is said to have the X-property w.r.t. < if for all n0, n1, n2, n3 ∈ V such that n0 < n1 and n2 < n3, if we have n0 R -→ n3 and n1 R -→ n2 then we also have n0 R -→ n2. H is said to have the X-property w.r.t. < if it is the case of each label R. Theorem 4.13. (Theorem 3.5 of [START_REF] Gottlob | Conjunctive queries over trees[END_REF], extending Theorem 3.1 of [START_REF] Gutjahr | Polynomial graph-colorings[END_REF]) Given a labeled query graph G, and given a labeled directed graph H with the X-property w.r.t. some order <, we can determine in time O(|H| × |G|) whether G ; H.

We can use this result to check, for all connected subpaths of the 2WP instance graph, whether the query graph has a homomorphism to the subpath. This leads to the following sketch for the proof of Proposition 4.11 (the full proof is in Appendix):

Proof sketch. We proceed following the three-step process outlined above. We first enumerate the possible query matches in the instance, i.e., the quadratic number of connected subpaths. Second, we test for each subpath ai -• • •a i+k whether it satisfies the query. We can do so tractably because the subpath clearly has the X-property w.r.t. the order ai < • • • < a i+k : using the notation of Definition 4.12, there are in fact no n0, n1, n2, n3 that satisfy the conditions. Third, having computed the resulting DNF, we compute its probability using β-acyclicity, eliminating variables in the order of the path as we explained above.

UNLABELED CONNECTED QUERIES

We now turn to the unlabeled setting, whose classification is presented in Table 3. We start with an intractability result which follows directly from the well-known intractability of query evaluation in probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF]: Proposition 5.1 [START_REF] Suciu | Probabilistic Databases[END_REF]. The PHom L (1WP, Connected) problem is #P-hard.

Proof. Example 3.3 of [START_REF] Suciu | Probabilistic Databases[END_REF] states that the conjunctive query ∃x∃y∃z U (x, y) ∧ U (y, z) is #P-hard on TID instances. In other words, PHom L ({→→}, All) is #P-hard, which implies the #P-hardness of PHom L (1WP, All). We conclude using Lemma 3.7, which provides a PTIME (Turing) reduction3 from the PHom L (1WP, Connected) problem to the PHom L (1WP, All) problem.

Note that this PHom L (1WP, Connected) problem can be phrased in a very simple way: given an unlabeled connected probabilistic graph (H, π) and a length m as input (namely, that of the 1WP graph query), compute the probability that H contains a directed path of length m.

This result suggests that, to obtain tractability, we need to restrict the instance graphs. In fact, such tractability results were already obtained in the previous sections. In Section 3, we proved (Proposition 3.6) that PHom L (All, DWT) has PTIME combined complexity. Similarly, in the previous 2WP) is also PTIME. This completes the analysis of the unlabeled case for 1WP, 2WP and DWT instances (see Table 3), so the only remaining case is that of PT instances.

We start our study of PHom L for PT instances with the simplest queries, namely, 1WP, for which we will show tractability. We will proceed by translating the 1WP query to a bottom-up deterministic tree automata [START_REF] Comon | Tree automata: Techniques and applications[END_REF]: Definition 5.2. Given an alphabet Γ, a bottom-up deterministic tree automaton on full binary (every node has either 0 or 2 children) rooted trees whose nodes are labeled by Γ is a tuple A = (Q, F, ι, ∆), where:

(i) Q is a finite set of states; (ii) F ∈ Q is a subset of accepting states; (iii) ι : Γ → Q is an initialization function determining the state of a leaf from its label; (iv) ∆ : Γ × Q 2 → Q is a transition function determining
the state of an internal node from its label and the states of its two children.

Given a Γ-tree T, λ (where λ : T → Γ is the labeling function), we define the run of A on T, λ as the function ϕ : T → Q such that (1) ϕ(l) = ι(λ(l)) for every leaf l of T ; and (2) ϕ(n) = ∆(λ(n), ϕ(n1), ϕ(n2)) for every internal node n of T with children n1 and n2. The automaton A accepts T, λ if its run on T maps the root of T to a state of F .

We will evaluate 1WP queries by translating them to a tree automaton and running it on an uncertain tree. This will use again the notion of lineage (recall Definition 4.6), which was extended in [START_REF] Amarilli | Provenance circuits for trees and treelike instances[END_REF] to tree automata running on trees with uncertain Boolean labels: the lineage of an automaton on such a tree describes the set of annotations of the tree that makes the automaton accept. In this context, the lineage of deterministic tree automata was shown in [START_REF] Amarilli | Tractable lineages on treelike instances: Limits and extensions[END_REF] to be compilable to a deterministic decomposable negation normal form circuit [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF]: Definition 5.3. A deterministic decomposable negation normal form (d-DNNF) is a Boolean circuit C with the following properties:

(i) negations are only applied to input gates; (ii) the inputs of any AND-gate depend on disjoint sets of input gates; (iii) the inputs of any OR-gate are mutually exclusive, i.e., for any two input gates g1 = g2 of g, there is no valuation of the inputs of C under which g1 and g2 both evaluate to true.

We can then straightforwardly extend the Boolean probability computation problem (Definition 4.2) to take circuits as inputs, and the properties of d-DNNF circuits are designed to ensure that the Boolean probability computation problem restricted to d-DNNF has PTIME complexity [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF]. Combining these tools, we can show that PHom L on one-way path queries and polytree instances is tractable:

Proposition 5.4. PHom L (1WP, PT) is PTIME.
Proof sketch. The idea of the proof is to construct in polynomial time in the query graph G a bottom-up deterministic automaton AG, which runs on binary trees T representing possible worlds of the polytree instance H, and accepts such a tree T iff the corresponding possible world satisfies G. We can then construct a d-DNNF representation of the lineage of G on H by [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF]Theorem 6.11], which allows us to efficiently compute Pr(G ; H): the complexity of this process is in O(|AG| • |H|), hence polynomial in |H| • |G|. (An alternative way to see this is to use the results of [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF].)

Intuitively, the design of the bottom-up automaton ensures that, when it reaches a node n after having processed the subtree Tn rooted at n, its state reflects three linear-sized quantities about Tn:

1. the length of the longest path leading out of n; 2. the length of the longest path leading to n; 3. the length of the longest path overall in Tn (not necessarily via n). The final states are those where the third quantity is greater than the length of G. The transitions compute each triple from the child triples by considering how the longest leading paths are extended, and how longer overall paths can be formed by joining an incoming and outgoing path.

Hence, PT instances enjoy tractability for the simplest query graphs. We now study whether this result can be extended to more general queries. We first notice that this result immediately extends to branching (i.e., to DWT queries), and even to unions of DWT queries. Indeed, in the unlabeled setting, as we already observed at the end of Section 3.1, such queries are equivalent to 1WP queries: Proposition 5.5. The problems PHom L (DWT, PT) and PHom L ( DWT, PT) are PTIME.

Proof. We first show the result for a DWT query graph G. Let m be its height, i.e., the length of the longest directed path it contains, and let G be the 1WP of length m, which can be computed in PTIME from G. It is easy to observe that G and G are equivalent. Indeed, we can find G as a subgraph of G by taking any directed path of maximal length, and conversely there is a homomorphism from G to G : map the root of G to the first vertex of G and each element of G at distance i from the root to the i-th element of G . Hence, PHom L on G and an input probabilistic PT instance reduces to PHom L on G and the same instance, so that the result follows from Proposition 5.4.

The same argument extends to DWT by considering the greatest height of a connected component of G.

Thus, we have successfully extended from 1WP to DWT queries while preserving tractability on PT instances. However, as we now show, tractability is not preserved if we extend queries to allow two-wayness. Indeed: Proposition 5.6. PHom L (2WP, PT) is #P-hard.

Proof. We adapt the proof of Proposition 4.1, but we face the additional difficulty of not being allowed to use labels. Fortunately, we can use the two-wayness in the query graph to simulate labels.

We reduce from #PP2DNF (recall Definition 4.3): the input consists of two disjoint sets X = {X1, . . . , Xn 1 }, Y = {Y1, . . . , Yn 2 } of Boolean variables, and a PP2DNF formula ϕ. We construct a 2WP query graph G and PT instance H with the same construction as the one that yielded H and G in that proof, except that we perform the following replacements (see Figure 8): In particular, the query graph is then defined as follows: G :=→→→ (→→←) m+3 →→→. All the edges of H have probability 1, except the middle edge of the edges that replaced the S-labeled edges used to code the valuation of the variables (e.g., for Xi, the middle edge of the 3 edges Xi →→← R), which have probability 1 2 . One can check that any image of G must again go from the vertex Ax j ,j to the vertex By j ,j for some 1 j m. The key insight is that the first → 5 of G must be matched to a → 5 -path in H , which only exist as the concatenation of a → 3 obtained by rewriting a T -edge for some variable Xj, and of the first → 2 of the (undirected) path from Xx j ,j to R. Then there is no choice left to match the next edges without failing.

From this we deduce that, from any possible world H W of the modified instance H , considering the corresponding possible world HW of the unmodified instance H following the natural bijection, the modified query graph G has a homomorphism to H W iff the unmodified query graph G has a homomorphism to HW. We thus conclude that the probabilistic homomorphism problem on G and H has the same answer as the one on G and H, which finishes the proof.

CONCLUSION

We have introduced the probabilistic homomorphism problem, also known in the database community as probabilistic evaluation of conjunctive queries on TID instances, and studied its combined complexity for various restricted classes of query and instance graphs. Our classes illustrate the impact on PHom of various features: acyclicity, two-wayness, branching, connectedness, and labeling. As we show, the landscape is already quite enigmatic, even for those seemingly restricted classes! In particular, we have identified four incomparable maximal tractable cases, reflecting various tradeoffs between the expressiveness that we can allow in the queries and in the instances:

• arbitrary queries on unlabeled downward trees (Proposition 3.6); • one-way path queries on labeled downward trees (Proposition 4.10); • connected queries on two-way labeled path instances (Proposition 4.11); • downward tree queries on unlabeled polytrees (Proposition 5.5);

H : R X1 X2 Y1 Y2 X1,3 X1,2 X1,1 X2,3 X2,2 X2,1 Y1,1 Y1,2 Y1,3 Y2,1 Y2,2 Y2,3 A1,1 A1,2 A2,3 B1,2 B2,1
B2,3 G : →→→ (→→←) 6 →→→ Figure 8: Illustration of the proof of Proposition 5.6 for the PP2DNF formula X1Y2 ∨ X1Y1 ∨ X2Y2. Dashed edges have probability 1 2 , all the others have probability 1.

These results all extend to disconnected instances, as shown in Section 3.3. The (somewhat sinuous) tractability border is described in Tables 1,2, and 3.

It is debatable whether the tractable classes we have identified yield interesting tractable cases for practical applications. The settings of Propositions 3.6, 5.5, and 4.11 may look restrictive, as both labels and branching are important features of real-world instances, though some situations may involve unlabeled tree-like instances, or labeled words. The setting of Proposition 4.10 may be richer, and is reminiscent of probabilistic XML [START_REF] Kimelfeld | Probabilistic XML: models and complexity[END_REF]: the instance is a labeled (downward) tree, while the query is a path evaluated on that tree.

Future work. The query and instance features studied in this paper could be completed by other dimensions: e.g., studying an unweighted case inspired by counting CSP where all probabilities are 1/2 (as our hardness proofs seem to heavily rely on some edges being certain); imposing symmetry in the sense of [START_REF] Beame | Symmetric weighted first-order model counting[END_REF]; or alternatively restricting the degree of graphs (though all our hardness proofs on polytrees and lower classes can seemingly be modified to work on bounded-degree). Another option would be to modify some of the existing dimensions: first, polytrees could be generalized to bounded-treewidth instances, as we believe that the relevant tractability result (Proposition 5.5) adapts to this setting; second, non-branching instances could be generalized to bounded-pathwidth instances, or maybe general instances with the X-property (recall Definition 4.12).

Of course, another natural direction would be to lift the arity-two restriction, although it is not immediate to generalize the definition of our classes to work in higher arity signatures. We could also extend the query language: in particular, allow unions of conjunctive queries as in [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF]; allow a descendant axis in the spirit of XML query languages [START_REF] Benedikt | XPath leashed[END_REF]; or more generally allow fixpoint constructs as done in [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits[END_REF] in the non-probabilistic case. An interesting question is whether an extended query language could capture the tractability results obtained in the context of probabilistic XML by [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF] (remembering, however, that such results crucially depend on having an order relation on node children [START_REF] Amarilli | The possibility problem for probabilistic XML[END_REF]). Another possibility would be to search for extensions of the β-acyclicity approach, and investigate which restrictions on the queries and instances ensure that the lineages are β-acyclic.

Last, the connection to CSP would seem to warrant further investigation. In particular, we do not know whether one could show a general dichotomy result on the combined complexity of query evaluation on TID instances, to provide a probabilistic analogue to the Feder-Vardi conjecture [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory[END_REF].

APPENDIX A. Proofs for Section 3 (DISCONNECTED CASE)

Proposition 3.6. PHom L (All, DWT) is PTIME.

Proof. Let G be an arbitrary unlabeled graph and (H, π) a probabilistic graph with H ∈ DWT. We observe that if G contains a directed cycle, then it cannot have a homomorphism to a subgraph of H (which is necessarily acyclic), so Pr(G ; H) = 0. Hence, it suffices to study the case where the query graph G is a DAG.

Likewise, if there are two vertices u, v of G and directed paths χ, χ in G from u to v such that χ and χ have different lengths, then again G cannot have a homomorphism to a subgraph of H: indeed, any subgraph of H is a directed forest and there is at most one directed path between each pair of nodes. So we can assume without loss of generality that there is no such pattern in G, and G is therefore graded.

Letting µ be a level mapping of G, we call the difference of levels of µ the difference between the largest and smallest value of its image; the difference of levels of G itself is the minimum difference of levels of a level mapping of G. As the level mappings of G only differ in the constant value that they add to all vertices of each connected component, the difference of levels can clearly be computed in PTIME by shifting each connected component so that its minimal level is zero, and computing the difference; we call the result of the shifting the minimal level mapping of G.

Letting m be the difference of levels of G, we now make the following claim: in any subgraph H of H, there is a homomorphism from G to H if and only if H has a directed path of length m.

This claim implies the result. Indeed, we can first check in PTIME if G has no cycles and has no pairs of paths of different lengths between two endpoints, and return 0 if the conditions are violated. We can then compute in PTIME the difference of levels m of G using the observations above. Now, on any subgraph of H, the query G is equivalent to the 1WP graph → m , so our result follows from Proposition 5.5.

All that remains is to prove the claim. We first note that it suffices to show the claim under the assumption that G is connected. Indeed, if the claim is true for all connected G, then the claim is implied for arbitrary G by considering each of its connected components, applying the claim, and observing that G has a suitable homomorphism to H iff each one of its connected components does, i.e., iff H has a directed path whose length is the maximal difference of levels of a connected component of G, and this is precisely the difference of levels m of G. Hence, we now prove the claim for connected G.

We start with the backwards direction of the claim. It is easily seen that there is a homomorphism h from G to the 1WP graph → m . Indeed, we define h according to the minimal level mapping µ of G: we set h to map all the vertices whose level is i to the i-th vertex of → m . From the existence of h , we know that, whenever there is a homomorphism h from → m to H , then h • h is a homomorphism from G to H , which shows the backwards implication.

For the forward direction of the claim, suppose that there exists a homomorphism h from G to H , and let m be the difference of levels of G. Because G is connected and H is in DWT, the image of h is actually a DWT, call it T . Now it is easy to see that the image of a node that has level m -i in G has depth i in T , so that T (and so H ) contains the 1WP → m . This finishes the proof of the converse and thus the proof of Proposition 3.6.

B. Proofs for Section 4 (LABELED CONNECTED QUERIES)

Proposition 4.1. PHom L (1WP, PT) is #P-hard.

Proof. We reduce from the #P-hard problem #PP2DNF. From the formula ϕ, we construct the following {S, T }-labeled probabilistic graph H (an example of this construction is presented in Figure 7):

• The vertices of H are {R} {X1, . . . Xn 1 } {Y1, . . . , Yn 2 } {Xi,j | 1 i n1, 1 j m} {Yi,j | 1 i n2, 1 j m} {Ax j ,j | 1 j m} {By j ,j | 1 j m}.

• The edges of H, all of which have probability 1 except when specified, are:

-Xi S -→ R for all 1 i n1 and R S -→ Yi for all 1 i n2, all having probability 1 2 and intuitively coding the valuation of each variable; -For all 1 i n1, the edge Xi,m S -→ Xi and the edges Xi,j S -→ Xi,j+1 for all 1 j m -1; -For all 1 i n2, the edge Yi -→. It is clear that G is a 1WP query graph, H is a polytree and that both can be constructed in PTIME from ϕ. We now show that Pr(G ; H) is exactly the number of satisfying assignments of ϕ divided by 2 n , so that the computation of one reduces in PTIME to the computation of the other, concluding the proof. To see why, we define a bijection between the valuations ν of {X1, . . . , Xn 1 } {Y1, . . . , Yn 2 } to the possible worlds H of H that have non-zero probability, in the expected way: keep the edge Xi S -→ R (resp., R S -→ Yi) iff Xi (resp., Yi) is assigned to true in the valuation. We then show that there is a homomorphism from G to H if and only if ϕ evaluates to true under ν.

Indeed, if there is a homomorphism from G to H , then by considering the only possible matches of the T -edges, one can check easily that the image of the match in H must be of the following form for some 1 j m: Ax

j ,j T -→ Xx j ,j S -→ Xx j ,j+1 S -→ • • • S -→ Xx j ,m S -→ Xx j S -→ R S -→ Yy j S -→ Yy j ,1 S -→ Yy j ,2 S -→ • • • S -→ Y y j ,j
T -→ B y j ,j ; further, from the length of the S-path we must have (m -j) + 4 + (j -1) = m + 3, so that we must have j = j . Then, by construction, Xx j and Yy j belong to clause j, so the valuation satisfies ϕ. Conversely, suppose that the valuation satisfies ϕ, then for some 1 j m we know that Xx j and Yy j are assigned to true by the valuation, and so we can build the homomorphism as above from G to H . Proposition 4.4 [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]. PHom L (DWT, DWT) is #P-hard.

Proof. The proof is almost the same as that of Proposition 36 of [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF], straightforwardly adapted to our setting of probabilistic graphs (in particular replacing the unary relation R by a binary relation), by observing that the probabilistic instance defined in this proof is actually a DWT (beyond having treewidth 1), and that the query actually corresponds to a DWT graph (beyond being α-acyclic).

Proposition 4.5 [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF]. PHom L (2WP, DWT) is #P-hard.

Proof. The proof is almost the same as that of Proposition 38 of [START_REF] Amarilli | Combined tractability of query evaluation via tree automata and cycluits (extended version)[END_REF], again adapted to our setting of probabilistic graphs, with one small modification: we do not materialize edges b Proof. We reduce our Boolean probability computation problem to the problem of β-acyclic #CSP d of [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF], which they show to be in PTIME (Theorem 26 of [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF]). We will explain how probability computation in the sense of Definition 4.2 can be encoded in their setting, by a variant of their own encoding (in Lemma 3 of [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF]): we give a full proof for completeness.

First, we recall their definition of #CSP d (Definitions 1 and 2 in [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF]) in the case of a Boolean domain. We denote by Q+ the nonnegative rational numbers. Denote by {0, 1} X the set of functions from X to {0, 1}, i.e., the Boolean valuations of X . For ν ∈ {0, 1} X and Y ⊆ X , we denote by ν |Y the restriction of ν to Y. A weighted constraint (with default value) on variables X is a pair c = (f, µ) that consists of a function f : S → Q+ for some subset S of {0, 1} X , called the support of c, and a default value µ ∈ Q+; we write var(c) := X . The constraint c induces a total function on {0, 1} X , also denoted c, that maps ν ∈ {0, 1} X to f (ν) if ν ∈ S, and to µ otherwise. The size of c is |c| = |S| × |X |. Intuitively, a constraint with default value assigns a weight in Q+ to all valuations of X , but the default value mechanism allows us to avoid writing explicitly the complete table of this mapping.

An We now explain how to reduce the probability computation problem to the β-acyclic #CSP d problem. Let ϕ = 1 i m 1 j n i Xi,j be a Boolean β-acyclic DNF on variables X , with probabilities π(X) ∈ [0, 1] for each X ∈ X . We construct in linear time from ϕ and π the variable set X := {X | X ∈ X }, the CNF formula ϕ := 1 i m 1 j n i X i,j , and the probability valuation π on X defined by π (X i,j ) = 1 -π(Xi,j). By De Morgan's duality law, ϕ is equivalent to the negation of ϕ, so that we have Pr(ϕ, π) = 1 -Pr(ϕ , π ); hence, the probability computation problem for ϕ and π reduces in PTIME to the same problem for ϕ and π .

We then construct in linear time a β-acyclic #CSP d instance I such that Pr(ϕ , π ) = w(I), which concludes the proof. For each variable X ∈ X , we define a weighted constraint c X on variables {X } by c X (X → 1) = π (X ) and c X (X → 0) = 1 -π (X ), which codes the probability of the variables. Now, for each clause 1 i m, just like in Lemma 3 of [START_REF] Brault-Baron | Understanding model counting for β-acyclic CNF-formulas[END_REF], we define a weighted constraint ci = (fi, 1) with default value 1 whose variables are {X i,j | 1 j ni}, i.e., those that occur in the clause: fi(ν) is 0 for the (unique) valuation that sets all variables of the clause to 0, intuitively coding the constraint of the clause. From the fact that ϕ was β-acyclic, it is clear that I is also β-acyclic. Now, the result w(I) of the partition function sums over all valuations of the variables of I, namely the variables X of ϕ . Whenever a valuation does not satisfy some clause 1 i m, the weighted constraint ci will give it weight 0, hence ensuring that the product evaluates to 0, so we can restrict the sum to valuations that satisfy ϕ : such valuations are given weight 1 by all weighted constraints ci. Now, it is easy to see that the weight of valuations ν that satisfy ϕ is their probability π (ν), as each c X gives them weight π (X ) or 1-(π (X )) depending on whether ν(X ) is 1 or 0. Hence, we have reduced the probability computation problem for β-acyclic DNF formulas to β-acyclic #CSP d in PTIME, which concludes the proof.

Proof. Let G • • = u1 R 1 --→ • • • R m-1
----→ um be the 1WP query (where all Ri are not necessarily distinct), and H be the downwards tree instance. The idea is to construct the lineage of G on H as a β-acyclic DNF ϕ, so that we can conclude with Theorem 4.9. It is clear that any match of G can only be a downwards path of H, hence we construct ϕ as follows: for every downwards path a1

R 1 --→ • • • R m-1
----→ am of length m of H (their number is linear in |H| because each path is uniquely defined by the choice of am) check if the path is a match of G (i.e, check that Ri = R i for 1 i m -1), and if it is the case then create a new clause of ϕ whose variables are all the facts ai R i --→ ai+1 for 1 i m -1. The formula ϕ thus obtained is then a DNF representation of the lineage of H on G, and has been built in time O(|H| • |G|), i.e., in PTIME. We now justify that ϕ is β-acyclic by giving a β-elimination order for ϕ: while H still has edges, repeatedly pick a leaf b of H and, letting a be the parent of b, eliminate the variable a R -→ b from ϕ. Such a variable will always be a β-leaf, as any set of downwards paths of a downwards tree all ending at a leaf is necessarily ordered by inclusion. From the above, the fact that ϕ is β-acyclic suffices to conclude the proof. Proof. First of all, notice that, as the query graph G is connected, the image of a homomorphism from the query G to the 2WP instance H is necessarily a connected component of H. Moreover, each connected component of H is also a 2WP and there are O(|H| 2 ) of them. We then proceed as follows. For every connected subpath C = a1 -• • • -an (with each -being either R -→ or R ← -for some binary relation R in H) of H, we check if there is a homomorphism from G to C. This can be done in PTIME by Theorem 4.13, because C trivially has the X-property w.r.t. the total order a1 < a2 < • • • < an: the only possibility for (n0, n3) and (n1, n2) to be edges of C when n0 comes before n1 and n2 comes before n3 is if n0 = n2 and n1 = n3, in which case it cannot hold that n0 R -→ n3 and n1 R -→ n2 at the same time, because we disallow multi-edges. If there is such a homomorphism, then we create a new clause of ϕ whose variables are all the facts that belong to C.

From this, we obtain in PTIME a positive DNF ϕ that captures the lineage of G on H. We now justify that ϕ is βacyclic by giving a β-elimination order for ϕ, by an argument similar to the proof of Proposition 4.10: repeatedly eliminate a variable a -b from ϕ and this fact from H, where b is an endpoint of H. Indeed such a variable will always be a β-leaf, as any set of connected component of H including a -b is necessarily ordered by inclusion. Hence, ϕ is β-acyclic, which allows us to conclude.

C. Proofs for Section 5 (UNLABELED CON-NECTED QUERIES)

Proposition 5.4. PHom L (1WP, PT) is PTIME.

Proof. Let G, (H, π) be the 1WP query graph and the probabilistic PT instance, and m be the length of G. Then Pr(G ; H) is the probability that H contains a directed path of length at least m.

Because we will use automata that run on full binary trees, we will have to represent possible worlds of H as full binary trees. The first step is to transform in linear time H into a full binary polytree H by applying a variant of the left-childright-sibling encoding: in so doing, in addition to unlabeled edges of both orientations that exist in the polytree, we will also introduce some edges called ε-edges that are labeled by ε and whose orientation does not matter (so we see them as undirected edges and write them a -b); intuitively, the ε-edge a -b means that a and b are in fact the same. For a node a ∈ H and a child b of a, we say that b is an up-child of a if we have b → a and a down-child of a if we have a → b. We do this transformation by processing H bottom-up as follows:

• If n is a leaf node of H, then create a node n in H .

• If n is an internal node of H with up-children u1, . . . , u k and down-children d1, . . . , d l then, letting u 1 , . . . , u k and d 1 , . . . , d l be the corresponding nodes in H : create a node n in H and nodes n 1 , . . . , n k+l-2 with the following ε-edges: n -n 1 -. . . -n k+l-2 , all having probability 1. Create an edge u 1 → n whose probability is that of u1 → n. For 2 i k create an edge u i → n i-1 annotated with the same probability as ui → n. For 1 i l -1 create an edge n k-1+i → d i annotated with the same probability as n → d i , and finally create an edge n k-2+l → d l annotated with the same probability as n → d l . Last, if any node has exactly one children (specifically, n , in case k + l = 1), then create a node n in H and connect it with an ε-edge to the node.

One can check that H is indeed a full binary polytree (with some edges being labeled by ε and being undirected) and that Pr(G ; H) equals the probability that H contains a path of the form (→ - * ) m , that is, m occurrences of a directed edge → followed by some sequence of ε-edges -.

The second step is to transform in linear time H into a probabilistic tree T to which we can apply the construction of [START_REF] Amarilli | Provenance circuits for trees and treelike instances (extended version)[END_REF]. Specifically, T must be an ordered full binary rooted tree whose edges do not have a label or an orientation, but whose nodes n carry a label in some finite alphabet Γ (written λ(n), where λ is the labeling function) and with a probability value written π(n). Writing Γ := Γ × {0, 1} as in [START_REF] Amarilli | Provenance circuits for trees and treelike instances (extended version)[END_REF], the semantics of T is that it stands for a probability distribution on Γ-trees, i.e., trees T labeled with Γ × {0, 1}, which have same skeleton as T : for each node n of T , the corresponding node n in a possible world T has label (λ(n), 1) with probability π(n) and label (λ(n), 0) otherwise. We do this transformation by first adding a new root vertex to H with an ε-edge with probability 1 to the original root (this clearly does not change the probability that H has a path of the prescribed form), and then simply create T from H by assigning the label and probability of each node that is not the new root as the direction of its parent edge (in Γ • • = {↑, ↓, -}) and its probability (so the root of T has label -and probability 1).

Our last step is to construct a bDTA AG running on Γtrees such that for every possible world W of H , letting TW be its representation as a Γ-tree, AG accepts TW if and only if W contains a path of the form (→ - * ) m . The states of AG are of the form ↑: i, ↓: j, Max : k for 0 i, j k m, which ensures that AG is of size polynomial in |G| (and we will construct it in PTIME from G). The idea is that when a node n of TW will be in such a state, it will mean that:

• Letting Wn be the subinstance of W which is represented by the subtree of TW rooted at n, and letting rn be the root of Wn, the longest directed upwards path in Wn finishing at rn has length i (the path is the longest of the form (↑ - * ) * that ends at rn). • The longest directed downwards path in Wn beginning at rn has length j (the path is the longest of the form (↓ - * ) * that begins at rn). • The longest directed path in Wn has length k (the path is of the form (→ - * ) k and is the longest in Wn).

We now describe the initialization function ι of AG:

• ι((s, 0)) := ↑: 0, ↓: 0, Max : 0 for any s ∈ Γ.

• ι((-, 1)) := ↑: 0, ↓: 0, Max : 0 .

• ι((↑, 1)) := ↑: 1, ↓: 0, Max : 1 .

• ι((↓, 1)) := ↑: 0, ↓: 1, Max : 1 .

• ∆((↑, 1), ↑: i, ↓: j, Max : k , ↑: i , ↓: j , Max : k ) := ↑: i , ↓: 0, Max : k where i := min(m, max(i + 1, i + 1)) and k := min(m, max(i , i + j , i + j, k, k )).

• ∆((↓, 1), ↑: i, ↓: j, Max : k , ↑: i , ↓: j , Max : k ) := ↑: 0, ↓: j , Max : k where j := min(m, max(j + 1, j + 1)) and k := min(m, max(j , i + j , i + j, k, k )).

• ∆((-, 1), ↑: i, ↓: j, Max : k , ↑: i , ↓: j , Max : k ) := ↑: i , ↓: j , Max : k where i := max(i, i ) and j := max(j, j ) and k := min(m, max(k, k , i + j , i + j)).

• ∆((s, 0), ↑: i, ↓: j, Max : k , ↑: i , ↓: j , Max : k ) := ↑: 0, ↓: 0, Max : k where k := min(m, max(k, k , i + j , i + j)) for every s ∈ {-, ↑, ↓}.

The final state of AG are all the states ↑: i, ↓: j, Max : k such that k = m. One can check by a straightforward induction that the semantics of each state is respected, so that indeed the automaton tests the query G.

We conclude thanks to Proposition 3.1 of [START_REF] Amarilli | Provenance circuits for trees and treelike instances (extended version)[END_REF] by computing in linear time in |AG| and |H | a representation of the lineage on H of the query that checks whether the input contains a directed path of the form (→ - * ) m , and observe by Theorem 6.11 of [START_REF] Amarilli | Tractable lineages on treelike instances: limits and extensions[END_REF] that it is a d-DNNF. We then compute the probability of this d-DNNF [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF], yielding Pr(G ; H) in PTIME: this concludes the proof.

D. PROOF OF HARDNESS OF COUNTING EDGE COVERS

In this appendix, following the connection pointed out in [START_REF] Williams | Complexity of counting the number of edge covers of a graph[END_REF], we give a proof of the following strengthening of Theorem 3.2, which is independent from the proof of [START_REF] Khanna | Queries with difference on probabilistic databases[END_REF].

Theorem D.1. The #Bipartite-Edge-Cover problem is #P-complete. Hardness holds even for 2-3 regular bipartite undirected graphs that are planar.

Proof. Membership in #P is straightforward: the machine guesses a subset of edges and accepts in PTIME iff the subset is a matching. Hence, we focus on hardness.

Recall that 2-3 regular bipartite undirected graphs are bipartite undirected graphs Γ = (U V, E) where the degree of each vertex in U is 2 and that of each vertex in V is 3. We will show how the result derives from the holographic reduction results of [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF].

For t ∈ U V , we denote by E(t) the set of edges to which t is adjacent. For a valuation of the edges ν : E → {0, 1} and a vertex t, we write ν(E(t)) the multiset { {ν(e) | e ∈ E(t)} }. Then, restricted to 2-3 regular bipartite undirected graphs, our problem #Bipartite-Edge-Cover can be seen to be the same as #[0, 1, 1]|[0, 1, 1, 1]. Indeed, seeing a valuation ν of the edges as a set of edges, the value under the sum for a valuation ν will be 1 if and only if, for every vertex, there exists an adjacent edge such that ν(e) = 1, which exactly means that ν is an edge cover of Γ. Now, let us consider the problem #[1, 1, 0]|[1, 1, 1, 0]. As observed at the end of Section 8 of [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF], it is the reversal of the problem #[0, 1, 1]|[0, 1, 1, 1]. Indeed, the problem #[1, 1, 0]|[1, 1, 1, 0] amounts to counting the number of subsets S of edges such that, for every vertex v, there exists at least one edge adjacent to v that is not in S, i.e., that is in E \ S. But this means that #[1, 1, 0]|[1, 1, 1, 0] counts the number of sets S such that E \ S is an edge cover of Γ. As there is a trivial bijection between the sets S that are edge covers and the sets S such that E \ S is an edge cover, #Bipartite-Edge-Cover is PTIME-equivalent to #[1, 1, 0]|[1, 1, 1, 0] on 2-3 regular bipartite undirected graphs. The problem #[1, 1, 0]|[1, 1, 1, 0] is shown in [START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF][START_REF] Cai | Holographic reduction, interpolation and hardness[END_REF] to be #P-hard on 2-3 regular bipartite graphs (even when the graphs are additionally required to be planar), which concludes the proof.

Figure 1 :

 1 Figure 1: Example probabilistic graph H

Example 2 . 2 .

 22 Continuing the example, consider the PHom problem for the graph G : the example probabilistic graph (H, π) in Figure1. The graph G intuitively corresponds to the relational calculus query ∃xyzt R(x, y)∧S(y, z)∧ S(t, z). Of course, we can compute Pr(G ; H) by summing over the possible worlds of H, but this process is generally intractable. Here, by considering the possible matches of G in H, we can see that Pr(G ; H) = 0.7×(1-(1-0.1)×(1-0.8)).

Figure 2 :Figure 3 :

 23 Figure 2: Inclusions between classes of graphs

Figure 4 :

 4 Figure 4: Examples of unlabeled DWT (left) and PT (right)

Figure 5 : 2 .

 52 Figure 5: Illustration of the proof of Proposition 3.3, for the bipartite graph Γ. Dashed edges have probability 1 2 . We show (in parentheses) the edge of Γ coded by each V -labeled edge in the instance graph H, and the vertex of Γ coded by each 1WP component of the query graph G.

Figure 6 :

 6 Figure 6: A DAG with a level mapping (dashed lines), see Definition 3.5.

Figure 7 :

 7 Figure 7: Illustration of the proof of Proposition 4.3 for the PP2DNF formula X1Y2 ∨ X1Y1 ∨ X2Y2. Dashed edges have probability 1 2 , all others have probability 1.

•

  replace every edge a S -→ b of H and G by 3 edges a →→← b; • replace every edge a T -→ b of H and G by 3 edges a →→→ b.

S-→

  Yi,1 and the edges Yi,j S -→ Yi,j+1 for all 1 j m -1; -For all 1 j m, the edges Ax j ,j T -→ Xx j ,j and Yy j ,j T -→ By j ,j , intuitively indicating that variables Xx j and Yy j belong to clause j.The {S, T }-labeled graph G is then T

  a in the instance graph for each edge a S -→ b in the instance, and instead modify the query to replace all edges x S - --→ y by edges x S ← -y. This ensures that the query is a 2WP and the instance is a DWT, and hardness is shown similarly to the original proof.

Theorem 4 . 9 .

 49 The Boolean probability computation problem is in PTIME when restricted to β-acyclic positive DNF formulas.

  instance of the #CSP d problem then consists of a finite set I of weighted constraints. The size of I is |I| := c∈I |c|, and we write var(I) := c∈I var(c). The output of the problem is the partition function w(I) = ν∈{0,1} var(I) c∈I c(ν |var(c) ). The hypergraph H(I) of the #CSP d instance I (defined in Section 2.2 of [11]) is the hypergraph (var(I), EI ) where EI = {var(c) | c ∈ I}. We say that I is β-acyclic if H(I) is a β-acyclic hypergraph (recall Definition 4.7), and we call β-acyclic #CSP d the problem #CSP d restricted to β-acyclic instances. By Theorem 26 of [11], the problem β-acyclic #CSP d is in PTIME.

Proposition 4 . 10 .

 410 PHom L (1WP, DWT) is PTIME.

Proposition 4 . 11 .

 411 PHom L (Connected, 2WP) is PTIME.

  Given a multiset of bits B, the Hamming weight of B is the number of 1 bits in B. For each x0, . . . , xn ∈ {0, 1}, let [x0, . . . , xn] denote the function that takes a multiset of n bits as input and outputs xi if the Hamming weight of those n bits is i. For every x0, x1, x2, y0, y1, y2, y3 ∈ {0, 1}, the problem #[x0, x1, x2]|[y0, y1, y2, y3] is the following [14]: given a 2-3 regular bipartite undirected graph Γ = (U V, E), compute the quantity ν:E→{0,1} u∈U [x0, x1, x2](ν(E(u))× v∈V [y0, y1, y2, y3](ν(E(v))).

Table 1 :

 1 Tractability of PHom L for disconnected queries (Section 3.2). Results also hold when instances are unions of the indicated classes. -hard Numbers given correspond to propositions for border cases, remaining cells can be filled using the inclusions from Figure2.

	↓G	H→ 1WP 2WP DWT PT Connected
	1WP	5.1
	2WP	3.4
	DWT	5.5
	PT
	All		3.6
	PTIME #P

Table 2 :

 2 Tractability of PHom L in the connected case We last discuss the case when both the query and instance graphs are disconnected. Let us consider the results of Table 1 for connected instance graphs. Clearly, any hardness results of a connected class carries over to the corresponding disconnected class. Conversely, we have shown in Proposition 3.6 that PHom L (All, DWT) is PTIME; this implies that all tractable cases in Table 1 also hold for unions of the indicated instance classes, except PHom L ( 1WP, PT) and PHom L ( DWT, PT). But we have noted at the end of Section 3.1 that, in the unlabeled setting, 1WP or DWT query graphs are equivalent to 1WP query graphs: thus, Lemma 3.7, together with tractability of PHom L (1WP, PT), implies PHom L ( 1WP, PT) and PHom L ( DWT, PT) are both in PTIME. Hence, the results of Table 1 also hold when instances are unions of the indicated classes.

	(Section 4)
	↓G	H→ 1WP 2WP DWT PT Connected
	1WP	4.10	4.1
	2WP	4.5
	DWT	4.4
	PT
	Connected	4.11
	PTIME #P-hard Numbers given correspond to proposi-
	tions for border cases, remaining cells can be filled using the
	inclusions from Figure 2.

Table 3 :

 3 Tractability of PHom L in the connected case , we proved that PHom L (Connected, 2WP) is PTIME (Proposition 4.11), which means PHom L (Connected,

	(Section 5)
	↓G	H→ 1WP 2WP DWT PT Connected
	1WP		5.1
	2WP		5.6
	DWT		5.5
	PT
	Connected	4.11	3.6
	PTIME #P-hard Numbers given correspond to proposi-
	tions for border cases, remaining cells can be filled using the
	inclusions from Figure 2.

section

#P is the class of counting problems that can be expressed as the number of accepting paths of a nondeterministic polynomial-time Turing machine.

The connection to β-acyclicity in this context is due to Florent Capelli.

Note that it is usual to define #P-hardness under Turing reductions rather than under Karp reductions, as #P is a counting complexity class.

Acknowledgements. We are grateful to Florent Capelli for pointing out to us the connection to β-acyclic instances and suggesting the idea used in the proof of Proposition 4.10, and to Tyson Williams for explaining the connection to holographic algorithms, in a very informative CSTheory post [35]. We also thank anonymous referees for their valuable feedback. This work was partly funded by the Télécom ParisTech Research Chair on Big Data and Market Insights.