Finding Degree-Constrained Acyclic Orientations

We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex ν is in a prescribed list λ(ν). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem...