I have a family of directed graphs over the same set of nodes $V$ defined as follows.
Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a relation $\rho\colon V \to 2^{V}$ such that $|\rho(v)| = k_v$ (where $\rho(v) = \{S \subset V \mid (v, S) \in \rho\}$, I'm abusing the relation notation a little bit). This relation induces a family of graphs: if we pick one predecessor set $S_v \in \rho(v)$ for each $v$, we obtain a fixed set of edges $E = \{ (u, v) \mid u \in S_v \}$ for the entire graph.
There are $\prod\limits_{v \in V} k_v$ such possible graphs, some of them are acyclic, some are not. I want to find at least one acyclic graph among these possibilities, and sort it topologically. Can it be done in polynomial time (i.e., faster than enumerating all possible combinations of choices explicitly)?
(As an illustrative application, imagine a package manager where some packages depend on either one of these other packages, because they all provide similar capabilities.)