  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 (ICDT'20). 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 (ICDT'21), along with new techniques.

Databases;Computational Complexity;Discrete Mathematics;Data Structures and Algorithms;Logic in Computer Science