  Query evaluation over probabilistic databases is known to be intractable in
many cases, even in data complexity, i.e., when the query is fixed. Although
some restrictions of the queries [19] and instances [4] have been proposed to
lower the complexity, these known tractable cases usually do not apply to
combined complexity, i.e., when the query is not fixed. This leaves open the
question of which query and instance languages ensure the tractability of
probabilistic query evaluation in combined complexity.
  This paper proposes the first general study of the combined complexity of
conjunctive query evaluation on probabilistic instances over binary signatures,
which we can alternatively phrase as a probabilistic version of the graph
homomorphism problem, or of a constraint satisfaction problem (CSP) variant. We
study the complexity of this problem depending on whether instances and queries
can use features such as edge labels, disconnectedness, branching, and edges in
both directions. We show that the complexity landscape is surprisingly rich,
using a variety of technical tools: automata-based compilation to d-DNNF
lineages as in [4], \b{eta}-acyclic lineages using [10], the X-property for
tractable CSP from [24], graded DAGs [27] and various coding techniques for
hardness proofs.
