Complexity of acyclicity of a "nondeterministic" graph By &quot;nondeterministic&quot; I mean the graph is a collection of sets of &quot;candidate&quot; 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!
The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.
The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, force every candidate edge that could begin at the vertex $v_0$ to begin there. If no such $v_0$ exists, then there is no solution.