2
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – zeb Aug 15 '20 at 5:16
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.