Best of the Rest: Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability

Query evaluation over tuple-independent probabilistic databases (TIDs) is notoriously intractable—not only in combined complexity, but often in data complexity as well. This motivates the study of approximation algorithms, and particularly of combined FPRASes, with runtime polynomial in both the query and instance size. In this paper, we focus on tuple-independent probabilistic databases over binary signatures, i.e., probabilistic graphs, and study when we can devise combined FPRASes for probabilistic query evaluation. In other words, we study FPRASes for probabilistic graph homomorphism, which is the equivalent analogue of conjunctive query evaluation: given a (deterministic) query graph 𝐺, and given an instance graph 𝐻 whose edges are annotated with independent probabilities (like a TID), we wish to approximate the probability that a randomly selected subgraph 𝐻 ′ ⊆ 𝐻 admits a homomorphism from 𝐺.