@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@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.
  },
}