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.