# Complexity of acyclicity of a “nondeterministic” graph

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!

• If every candidate set has bounded size, then this falls into the framework of Temporal CSPs: for instance, a nondeterministic edge ({a,b,c},d) corresponds to the constraint ((a < d) OR (b < d) OR (c < d)). The boundary between NP-hard and polynomial time solvable Temporal CSPs is known (see "The Complexity of Temporal Constraint Satisfaction Problems" by Bodirsky and Kara), which gives us a place to start with this question. – zeb Aug 15 '20 at 5:16

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.