2026-07-26T00:39:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17756 2024-03-06T11:00:24Z ddc:004 open_access

Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries Amarilli, Antoine Uniform reliability #P-hardness probabilistic databases We study the uniform query reliability problem, which asks, for a fixed Boolean query Q, given an instance I, how many subinstances of I satisfy Q. Equivalently, this is a restricted case of Boolean query evaluation on tuple-independent probabilistic databases where all facts must have probability 1/2. We focus on graph signatures, and on queries closed under homomorphisms. We show that for any such query that is unbounded, i.e., not equivalent to a union of conjunctive queries, the uniform reliability problem is #P-hard. This recaptures the hardness, e.g., of s-t connectedness, which counts how many subgraphs of an input graph have a path between a source and a sink. This new hardness result on uniform reliability strengthens our earlier hardness result on probabilistic query evaluation for unbounded homomorphism-closed queries [Amarilli and Ceylan, 2021]. Indeed, our earlier proof crucially used facts with probability 1, so it did not apply to the unweighted case. The new proof presented in this paper avoids this; it uses our recent hardness result on uniform reliability for non-hierarchical conjunctive queries without self-joins [Antoine Amarilli and Benny Kimelfeld, 2022], along with new techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.14 urn:nbn:de:0030-drops-177566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.14 eng https://creativecommons.org/licenses/by/4.0/legalcode