• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Approximating Queries on Probabilistic Graphs
Antoine Amarilli, Timothy van Bremen, Octave Gaspard and Kuldeep S. Meel.
Logical Methods in Computer Science, 21(4), 2025.
Query evaluation over probabilistic databases 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. We settle the complexity of this problem for a variety of query and instance classes, by proving both approximability results and (conditional) inapproximability results together with (unconditional) DNNF provenance circuit size lower bounds. This allows us to deduce many corollaries of possible independent interest. For example, we show how the results of Arenas et al. [ACJR21a] on counting fixed-length strings accepted by an NFA imply the existence of an FPRAS for the two-terminal network reliability problem on directed acyclic graphs, a question asked by Zenklusen and Laumanns [ZL11]. We also show that one cannot extend a recent result of van Bremen and Meel [vBM23] giving a combined FPRAS for self-join-free conjunctive queries of bounded hypertree width on probabilistic databases: neither the bounded-hypertree-width condition nor the self-join-freeness hypothesis can be relaxed. We last show how our methods can give insights on the evaluation and approximability of regular path queries (RPQs) on probabilistic graphs in the data complexity perspective, showing in particular that some of them are (conditionally) inapproximable.
@article{ABGM25,
title={Approximating Queries on Probabilistic Graphs},
author={
Amarilli, Antoine and van Bremen, Timothy and Gaspard, Octave and Meel,
Kuldeep S.
},
journal={Logical Methods in Computer Science},
volume={21},
number={4},
year={2025},
bib2html_rescat={Counting},
bib2html_pubtype={Journal},
bib2html_dl_pdf={https://doi.org/10.46298/lmcs-21(4:30)2025},
abstract={
Query evaluation over probabilistic databases 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. We settle the
complexity of this problem for a variety of query and instance classes, by
proving both approximability results and (conditional) inapproximability
results together with (unconditional) DNNF provenance circuit size lower
bounds. This allows us to deduce many corollaries of possible independent
interest. For example, we show how the results of Arenas et al. [ACJR21a] on
counting fixed-length strings accepted by an NFA imply the existence of an
FPRAS for the two-terminal network reliability problem on directed acyclic
graphs, a question asked by Zenklusen and Laumanns [ZL11]. We also show that
one cannot extend a recent result of van Bremen and Meel [vBM23] giving a
combined FPRAS for self-join-free conjunctive queries of bounded hypertree
width on probabilistic databases: neither the bounded-hypertree-width
condition nor the self-join-freeness hypothesis can be relaxed. We last show
how our methods can give insights on the evaluation and approximability of
regular path queries (RPQs) on probabilistic graphs in the data complexity
perspective, showing in particular that some of them are (conditionally)
inapproximable.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21