4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you summarize the bottom-line result? Can the problem be solved for directed graphs? What is the running time / complexity? Is it polynomial? $\endgroup$ – D.W. Apr 10 '14 at 17:47
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Apr 11 '14 at 4:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.