[Solved]: Construct a digraph given its in-degree and out-degree distribution

Problem Detail: 

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.

Asked By : Samy Arous

Answered By : Yuval Filmus

The following remarks are taken from a paper by Berger. I assume that you don't allow parallel loops.

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.

A similar criterion for the case in which loops are forbidden also exists, see Berger's paper quoted above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23575