<p>The strategy I outlined in the comment worked: reading through <a href="http://www.lix.polytechnique.fr/%7Ebodirsky/publications/tcsp.pdf" rel="noreferrer">Bodirsky and Kara</a>'s paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.</p>
<p>The algorithm they suggest is quite simple (in hindsight): look for a vertex <span class="math-container">$v_0$</span> which is never the target of any edge, and if you find one, force every candidate edge that <em>could</em> begin at the vertex <span class="math-container">$v_0$</span> to begin there. If no such <span class="math-container">$v_0$</span> exists, then there is no solution.</p>

CC BY-SA 4.0
2020-08-15T06:26:10.350Z
2020-08-15T06:26:10.350Z
zeb
<p>By &quot;nondeterministic&quot; I mean the graph is a collection of sets of &quot;candidate&quot; edges sharing a single destination: <span class="math-container">$E \subseteq 2^V \times V$</span>. The problem is whether it is possible to pick one edge from each candidate set, so that the picked edges form an acyclic graph.</p>
<p>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.</p>
<p>Does anyone know whether this problem has already been investigated? Is it NP hard?</p>
<p>Thanks!</p>

CC BY-SA 4.0
2020-08-15T05:16:07.177Z
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
<graph-theory><graph-algorithms><np-hardness><time-complexity><directed-acyclic-graph>
Complexity of acyclicity of a "nondeterministic" graph
exprosic
# Complexity of acyclicity of a "nondeterministic" graph

(Asked by: username_0 on 2020-08-14)

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!

**Tags:** graph-theory, graph-algorithms, np-hardness, time-complexity, directed-acyclic-graph
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2020-08-15. Score: 6 | Accepted answer

The strategy I outlined in the comment worked: reading through [Bodirsky and Kara](http://www.lix.polytechnique.fr/%7Ebodirsky/publications/tcsp.pdf)'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.


---

