  We study the following fundamental realization problem of directed acyclic
graphs (dags). Given a sequence S:=(a_1,b_1),...,(a_n, b_n) with a_i, b_i in
Z_0^+, does there exist a dag (no parallel arcs allowed) with labeled vertex
set V:= {v_1,...,v_n} such that for all v_i in V indegree and outdegree of v_i
match exactly the given numbers a_i and b_i, respectively? Recently this
decision problem has been shown to be NP-complete by Nichterlein (2011).
However, we can show that several important classes of sequences are
efficiently solvable.
  In previous work (Berger and Mueller-Hannemann, FCT2011), we have proved that
yes-instances always have a special kind of topological order which allows us
to reduce the number of possible topological orderings in most cases
drastically. This leads to an exact exponential-time algorithm which
significantly improves upon a straightforward approach. Moreover, a combination
of this exponential-time algorithm with a special strategy gives a linear-time
algorithm. Interestingly, in systematic experiments we observed that we could
solve a huge majority of all instances by the linear-time heuristic. This
motivates us to develop characteristics like dag density and "distance to
provably easy sequences" which can give us an indicator how easy or difficult a
given sequence can be realized.
  Furthermore, we propose a randomized algorithm which exploits our structural
insight on topological sortings and uses a number of reduction rules. We
observe that it clearly outperforms all other variants and behaves surprisingly
well for almost all instances. Another striking observation is that our simple
linear-time algorithm solves a set of real-world instances from different
domains, namely ordered binary decision diagrams (OBDDs), train and flight
schedules, as well as instances derived from food-web networks without any
exception.
