By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible to pick one edge from each candidate set, so that the picked edges form an acyclic graph.
When the candidate sets are all singletons, the graph is then deterministic and the problem is of course linear. The general case seems sufficiently complicated to be NP hard, but I couldn't prove it, nor did I find any related literature.
Does anyone know whether this problem has already been investigated? Is it NP hard?
Thanks!