# 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.

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)$. – Yuval Filmus Apr 11 '14 at 4:40