Construct a digraph given its in-degree and out-degree distribution

Could anyone help me with this algorithmic problem:

Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph can allow self loops but not parallel edges.

Here's an example:

Vertex A: in=1 out=1
Vertex B: int=2 out=2


For which we can construct this graph:

A => B
B => A
B => B


Here's another example:

Vertex A: in=0 out=1
Vertex B: in=1 out=1


Here, we obviously cannot construct such graph.

I have been scratching my head around this problem. For an undirected graph, there exist a simple algorithm to solve this problem but I cannot find any way to derive a solution for directed graphs.

I have the intuition that we could find a matching algorithm in the bipartite graph representing the in and out edges of the graph and where each out-edge would be matched to an in-edge.

However the usual approach can produce a graph with parallel edges.

For example 1, a valid solution could be:

A- A+: A => A
B- B+: B => B
B- B+: B => B


Which is not a valid graph.

Also, please note that I am more interested in determining if a valid solution exists. It's not necessary to provide or construct such solution.

• Can you mention the algorithm that exists for the undirected graphs? Commented Apr 9, 2014 at 1:41
• @emab This is the Erdős–Gallai theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem. Commented Apr 9, 2014 at 1:52

The idea is to frame the problem on bipartite graphs. One side of the bipartition consists of the "inside" of vertices, the other of the "outside". Each vertex $v$ has two copies $v_-,v_+$, and we want $d(v_-)$ to be the indegree of $v$, $d(v_+)$ to be the outdegree of $v$. The existence of such a bipartite graph is the the focus of the Gale–Ryser theorem, which gives an efficient algorithm.
• The problem is solvable for directed graphs in time $O(n^2)$ (if implementing the algorithms naively). It is probably possible to improve the running time to $O(n\log n)$. Commented Apr 11, 2014 at 4:40