arXiv:1708.05520v1 [cs.DS] 18 Aug 2017

An Optimal Realization Algorithm for Bipartite
Graphs with Degrees in Prescribed Intervals∗
Steffen Rechner
Institute of Computer Science
Martin Luther University Halle-Wittenberg, Germany
steffen.rechner@informatik.uni-halle.de

March 1, 2018

Abstract
We consider the problem of constructing a bipartite graph whose degrees lie in prescribed intervals. Necessary and sufficient conditions for
the existence of such graphs are well-known. However, existing realization algorithms suffer from large running times. In this paper, we
present a realization algorithm that constructs an appropriate bipartite
graph G = (U, V, E) in O(|U | + |V | + |E|) time, which is asymptotically
optimal. In addition, we show that our algorithm produces edge-minimal
bipartite graphs and that it can easily be modified to construct edgemaximal graphs.

1

Introduction

The construction of bipartite graphs with prescribed degrees is a well-studied
algorithmic problem with various applications in science. Whereas the classical
problem asks for a bipartite graph whose degrees must exactly match prescribed
integers, we study the problem of constructing a bipartite graph whose degrees
have to lie in prescribed intervals. As one application, the construction of such
graphs is part of several sampling algorithms that aim at producing random
bipartite graphs whose degrees lie in the prescribed intervals. Such sampling
algorithms typically work by randomly modifying an existing bipartite graph,
while preserving the prescribed bounds on the degrees [5]. If no bipartite graph
with prescribed degrees is given, the first step of such algorithms is to construct
an initial bipartite graph. In such cases, the efficient realization is of high
importance for the efficiency of the whole sampling algorithm.
∗ Submitted

to the Journal of Discrete Algorithms.

1

Problem Definition Given a four-tuple of integer vectors (r̃, r̄, c̃, c̄) with r̃ =
(r̃1 , r̃2 , . . . , r̃n1 ), r̄ = (r̄1 , r̄2 , . . . , r̄n1 ), c̃ = (c̃1 , c̃2 , . . . , c̃n2 ), c̄ = (c̄1 , c̄2 , . . . , c̄n2 ),
we want to construct a bipartite graph whose vertex degrees are bounded from
below by the vectors r̃ and c̃ and from above by r̄ and c̄. More precisely,
let dG : U ∪V → N describe the vertex degrees of a bipartite graph G = (U, V, E)
with disjoint vertex sets U = {u1 , u2 , . . . , un1 } and V = {v1 , v2 , . . . , vn2 }. We
seek a bipartite graph such that r̃i ≤ dG (ui ) ≤ r̄i and c̃j ≤ dG (vj ) ≤ c̄j hold for
all i in range 1 ≤ i ≤ n1 and j in range 1 ≤ j ≤ n2 .
Related Work In the special case of r̃ = r̄ and c̃ = c̄, Ryser’s algorithm [6] is
used for decades to construct a valid bipartite graph G = (U, V, E) in O(|U | +
|V | + |E|) time. In the general case, the problem can be solved by finding
a (g, f )-factor in the complete bipartite graph with g and f being integer vectors
obtained by concatenating the vectors of lower and upper bounds. As (g, f )factors in arbitrary graphs G = (V, E) can be constructed in O(|V|3 ) time [1], this
approach leads to a realization algorithm with a running time of O((|U |+|V |)3 ).
Another way of finding a valid bipartite graph is to construct an appropriate
flow network F = (V, A) and to calculate a maximal flow [2]. As calculating a
maximal flow can be achieved in O(|V| · |A|) time [4] and, in our case, the flow
network needs to have |V| = |U | + |V | + 2 vertices and |A| = |U | · |V | + |U | + |V |
arcs, we gain a running time of O(|U | · |V | · (|U | + |V |)).
Contribution In this article, we present a realization algorithm whose running time is bounded by O(|U |+|V |+|E|) with |E| being the number of edges of
the bipartite graph that is been constructed. After summarizing the necessary
theoretical background, we present the realization algorithm and show that its
running time is O(|U | + |V | + |E|). Finally, we show that the bipartite graph
constructed by our method is edge-minimal.

2

Preliminaries

Definitions Let n1 and n2 be positive integers. Let r = (r1 , r2 , . . . , rn1 ), r̄ =
(r̄1 , r̄2 , . . . , r̄n1 ), and c = (c1 , c2 , . . . , cn2 ) be integer vectors of length n1 respectively n2 . The integer vector r is called non-increasing if ri ≥ ri+1 for 1 ≤ i <
n1 . We say that the pair of integer vectors (r, c) is bi-graphical if and only if
there is a bipartite graph G = (U, V, E) such that dG (ui ) = ri and dG (vj ) = cj
for 1 ≤ i ≤ n1 and 1 ≤ j ≤ n2 . We will write r ≤ r̄ if and only if ri ≤ r̄i for
all i in range 1 ≤ i ≤ n1 . The integer vector c0 = (c01 , c02 , . . . , c0n1 ) of length n1
is called conjugate vector of c if and only if c0i = |{j : 1 ≤ j ≤ n2 ∧ cj ≥ i}| for
Pk
each i in range 1 ≤ i ≤ n1 . We abbreviate the sum i=1 ri by Σkr . We say that
the conjugate vector c0 dominates r and write r E c0 if and only if Σkr ≤ Σkc0
holds for 1 ≤ k ≤ n1 . In addition, we define Σr to be the vector of partial
sums of an integer vector r, thus Σr = (Σ1r , Σ2r , . . . , Σnr 1 ). Finally, we say that
the four-tuple of integer vectors (r̃, r̄, c̃, c̄) is realizable if and only if there is a
bipartite graph G = (U, V, E) such that r̃i ≤ dG (ui ) ≤ r̄i and c̃j ≤ dG (vj ) ≤ c̄j
2

hold for 1 ≤ i ≤ n1 and 1 ≤ j ≤ n2 . In such cases, we will call G a realization
of the four-tuple (r̃, r̄, c̃, c̄).
Our algorithm is based on the following well-known theorems.
Theorem 1 (Gale [3], Ryser [6]). Let r = (r1 , r2 , . . . , rn1 ) be a non-increasing
integer vector and let c = (c1 , c2 , . . . , cn2 ) be an integer vector. The pair (r, c)
is bi-graphical if and only if Σnr 1 = Σnc 2 and r E c0 .
Theorem 2 (Fulkerson [2], Schocker [7]). Let r̃ = (r̃1 , r̃2 , . . . , r̃n1 ) and c̃ =
(c̃1 , c̃1 , . . . , c̃n2 ) be non-increasing integer vectors, and let r̄ = (r̄1 , r̄2 , . . . , r̄n1 )
and c̄ = (c̄1 , c̄2 , . . . , c̄n2 ) be integer vectors with r̃ ≤ r̄ and c̃ ≤ c̄. The fourtuple (r̃, r̄, c̃, c̄) is realizable if and only if r̃ E c̄0 and c̃ E r̄0 .

3

Realization Algorithm

Our algorithm assumes that the integer vectors r̃ and c̃ are ordered non-increasingly, which can be easily arranged by descendingly sorting the pairs (r̃, r̄)
and (c̃, c̄) by their associated lower bounds. In addition, the algorithm assumes
that the four-tuple (r̃, r̄, c̃, c̄) is realizable, which can be verified by Theorem 2.
The key idea is now to iteratively construct a bi-graphical pair of integer vectors (r, c) bounded by r̃ ≤ r ≤ r̄ and c̃ ≤ c ≤ c̄ that is afterwards realized via
Ryser’s algorithm [3]. The algorithm is divided into two parts.

3.1

Phase One

Since the four-tuple (r̃, r̄, c̃, c̄) is realizable by assumption, there is a bipartite graph G = (U, V, E) such that c̃j ≤ dG (vj ) ≤ c̄j holds for each vj ∈ V .
As a consequence, there must be an integer vector c = (c1 , c2 , . . . , cn2 ) which
describes the degrees of vertex set V . With other words, there is an integer
vector c bounded by c̃ ≤ c ≤ c̄ such that (r̃, r̄, c, c) is realizable. In its first
phase (see Alg. 1), the algorithm constructs such a vector c. For this purpose, c
is initialized with c̃. In a series of iterations, the algorithm identifies the rightmost component ci with ci < c̄i and increments the left-most components cj
with cj = ci . After a well-chosen number δ1 of iterations, the algorithm returns
the realizable four-tuple (r̃, r̄, c, c).
Example

Consider the following integer vectors:
r̃ = (4, 1, 0) c̃ = (2, 2, 0, 0, 0)
r̄ = (4, 2, 3) c̄ = (2, 3, 1, 2, 2).

By setting up at the corresponding conjugate vectors, we observe that the fourtuple (r̃, r̄, c̃, c̄) is realizable via Theorem 2.
r̃ = (4, 1, 0)

r̄0 = (3, 3, 2, 1, 0)

c̃ = (2, 2, 0, 0, 0)

Σr̃ = (4, 5, 5)

Σr̄0 = (3, 6, 8, 9, 9)

Σc̃ = (2, 4, 4, 4, 4)
3

c̄0 = (5, 4, 1)
Σc̄0 = (5, 9, 10).

Algorithm 1: Phase One
Input: realizable four-tuple (r̃, r̄, c̃, c̄)
Output: realizable four-tuple (r̃, r̄, c, c) with c̃ ≤ c ≤ c̄
1 c ← c̃
// initialize c with lower bounds c̃
j
j
// calculate number of steps
2 δ1 ← max{Σr̃ − Σc̃0 : 1 ≤ j ≤ n1 }
3 i ← n2
// right-most position such that ci < c̄i
4 for k = 1, 2, . . . , δ1 do
5
while ci = c̄i do
// proceed to next position with ci < c̄i
6
i←i−1
7
end
8
j ← min{` : c` = ci }
// identify left-most cj with cj = ci
9
swap c̄i and c̄j
10
cj ← cj + 1
11 end
12 return (r̃, r̄, c, c)

The vector c is initialized with c ← c̃ = (2, 2, 0, 0, 0). As c̃0 = (2, 2, 0) and Σc̃0 =
(2, 4, 4), the number of steps of the outer loops is calculated by δ1 ← max{4 −
2, 5 − 4, 5 − 4} = 2.
1. The inner loop breaks with i = 5. The left-most component equal to c5 = 0
is at position j = 3. Thus, the algorithm swaps c̄5 and c̄3 and increments c3 . We gain c = (2, 2, 1, 0, 0) and c̄ = (2, 3, 2, 2, 1).
2. The inner loop breaks again with i = 5. The left-most component equal
to c5 = 0 is now at position j = 4. Thus, the algorithm swaps c̄5 and c̄4
and increments c4 . We gain c = (2, 2, 1, 1, 0) and c̄ = (2, 3, 2, 1, 2).
The situation at the end of the first phase:
r̃ = (4, 1, 0)

r̄ = (4, 2, 3)

c = (2, 2, 1, 1, 0)

c0 = (4, 2, 0)

Σr̃ = (4, 5, 5)

Σr̄ = (4, 6, 9)

Σc = (2, 4, 5, 6, 6)

Σc0 = (4, 6, 6).

We observe that (r̃, r̄, c, c) is realizable via Theorem 2.
Proof of Correctness The correctness of Alg. 1 follows from Lemma 3 and 4.
For the following theorems, let r̃ = (r̃1 , r̃2 , . . . , r̃n1 ) and c = (c1 , c2 , . . . , cn2 ) be
non-increasing integer vectors and let r̄ = (r̄1 , r̄2 , . . . , r̄n1 ) and c̄ = (c̄1 , c̄2 , . . . , c̄n2 )
be integer vectors such that r̃ ≤ r̄ and c ≤ c̄ hold, (r̃, r̄, c, c̄) is realizable,
and (r̃, r̄, c, c) is not realizable.
Lemma 3. There is a right-most position i with ci < c̄i . Let j be the left-most
position with cj = ci . Let a = (a1 , a2 , . . . , an2 ) and ā = (ā1 , ā2 , . . . , ān2 ) be

4

integer vectors defined by
(
ck + 1,
ak =
ck ,

if k = j,
otherwise,

and



c̄i ,
āk = c̄j ,


c̄k ,

if k = j,
if k = i,
otherwise.

Then, a is non-increasing, a ≤ ā holds, and (r̃, r̄, a, ā) is realizable.
Proof. As (r̃, r̄, c, c̄) is realizable by assumption and (r̃, r̄, c, c) is not, c cannot
be equal to c̄. Thus, there must be a position i with ci < c̄i . As j is chosen
left-most with cj = ci , either j = 1 or cj−1 > cj must hold. In both cases, the
integer vector a is non-increasing as c is non-increasing by assumption.
We show next that a ≤ ā holds. As ci < c̄i holds by assumption, it follows
that aj = cj + 1 = ci + 1 ≤ c̄i = āj . To see that ai ≤ āi holds, consider two
cases. If i = j, the inequality āi = c̄i ≥ ci + 1 = ai holds as ci < c̄i . Otherwise,
if i 6= j, we derive āi = c̄j ≥ cj = ci = ai . Hence, ai ≤ āi holds in both cases.
Since ak = ck and āk = c̄k for all k 6= i, j, we infer a ≤ ā.
It remains to show that (r̃, r̄, a, ā) is realizable. By Theorem 2, (r̃, r̄, a, ā)
is realizable if and only if r̃ E ā0 and a E r̄0 hold. Since ā is a permutation
of c̄, the sets {` : āi ≥ k} and {` : c̄i ≥ k} are identical for all k, thus, ā0
equals c̄0 . As r̃ E c̄0 holds due to the realizability of (r̃, r̄, c, c̄), the dominance
relation r̃ E ā0 holds, too.
Now assume that a E r̄0 does not hold. Thus, there is a right-most position k
such that Σka > Σkr̄0 . Since Σkc ≤ Σkr̄0 must hold as (r̃, r̄, c, c̄) is realizable and a
differs from c only at position j, we conclude Σkc = Σkr̄0 and j ≤ k. Next, we
show that i > k. Therefore, assume the contrary and let i ≤ k. Since i is
chosen right-most, it follows that c` = c̄` for each ` in range i < ` ≤ n2 . Thus,
increasing an arbitrary c` in range i < ` ≤ n2 by a positive amount would
violate c ≤ c̄ whereas increasing an arbitrary c` in range 1 ≤ ` ≤ i violates the
realizability of (r̃, r̄, c, c̄). Hence, (r̃, r̄, c, c̄) can only be realizable if (r̃, r̄, c, c)
is, which contradicts our assumption. Thus, i > k.
Since j was chosen left-most with cj = ci , we obtain from j ≤ k and k < i
that cj = . . . = ck = ck+1 = . . . = ci . Since k is right-most and (r̃, r̄, c, c̄) is
0
< Σk+1
holds and thus, r̄k+1
> ck+1 . As r̄0
realizable, we conclude that Σk+1
c
r̄0
0
0
is non-increasing by definition, we conclude further that r̄k ≥ r̄k+1
> ck+1 =
k−1
k
k
k−1
ck . Consequently, Σc = Σr̄0 holds if and only if Σc
> Σr̄0 holds, which
contradicts the realizability of (r̃, r̄, c, c̄) if k > 1, or is plainly wrong if k = 1.
As a consequence, a E r̄0 must hold and thus, (r̃, r̄, a, ā) is realizable.
Lemma 4. Let c(k) and c̄(k) be the state of the integer vectors c and c̄ after
exactly k iterations of the outer loop in Alg. 1. Then, (r̃, r̄, c(k) , c(k) ) is not
realizable unless k ≥ δ1 = max{Σjr̃ − Σjc̃0 : 1 ≤ j ≤ n1 }.
Proof. By Lemma 3, c(k) is non-increasing and c(k) ≤ c̄(k) holds. Hence, by
Theorem 2, the four-tuple (r̃, r̄, c(k) , c(k) ) is realizable if and only if r̃ E (c(k) )0
and c(k) ≤ r̄0 hold. Whereas the latter domination relation is ensured by
Lemma 3, the condition r̃ E (c(k) )0 will not hold if k < δ1 . To see why this is
5

(k)

true, consider incrementing an arbitrary component cj
Whereas the components

(c(k+1) )0`

(c(k+1) )0`

(k+1)

to cj

will be equal to (c(k) )0` for
value (c(k+1) )0` = (c(k) )0` +

(k)

= cj

each ` 6=

the component
will be of
1 for ` =
As a consequence, the partial sums Σc(k+1) are affected by
(
(k)
Σi(c(k) )0 + 1, if cj < i ≤ n1 ,
i
Σ(c(k+1) )0 =
Σi(c(k) )0 ,
otherwise.

+ 1.

(k+1)
cj
,
(k+1)
cj
.

Now let p be an arbitrary position such that Σpr̃ > Σpc̃0 holds at the beginning
of the first phase. Since Σpr̃ stays constant, the inequality Σpr̃ ≤ Σp(c(k) )0 will be
established as soon as a number of k ≥ Σpr̃ −Σpc0 components of value cj < p have
been incremented. As Alg. 1 chooses cj as small as possible, the domination
relation r̃ E (c(k) )0 will hold after exactly δ1 = max{Σjr̃ − Σjc̃0 : 1 ≤ j ≤ n1 }
iterations.
Running Time Determining the quantity δ1 requires a running time of O(n1 ).
The outer loop of Alg. 1 runs exactly δ1 steps. In each step, the algorithm has
to determine the position j ← min{` : c` = ci } of the left-most occurrence of
a component equal to ci . This can be achieved in constant time if we use a
pre-computed lookup-table which is updated after each incrementation. Fortunately, each increment operations only requires a table-update at the positions ci
and ci + 1 which can be executed in constant time. Thus, letting beside the
inner loop, each step of the outer loop is executed in constant time. In contrast,
the inner loop may need linear time. However, the variable i can be decreased
at most n2 times during the whole process. Thus, the running time of the outer
loop is O(n2 + δ1 ). In summary, since δ1 ≤ Σnr̃ 1 , the running time of the first
phase can be bounded by O(n1 + n2 + Σnr̃ 1 ).

3.2

Phase Two

After the first phase has stopped, r̃ and c are non-increasing integer vectors
and (r̃, r̄, c, c) is realizable by Lemma 3 and 4. Hence, there is a bipartite
graph G = (U, V, E) with dG (vj ) = cj for j in range 1 ≤ j ≤ n2 and r̃i ≤
dG (ui ) ≤ r̄i for i in range 1 ≤ i ≤ n1 . If we switch the roles of vertex
sets U and V , we gain an instance of the realization problem in which the
four-tuple (c, c, r̃, r̄) is realizable, c and r̃ are non-increasing, and r̃ ≤ r̄ holds.
Thus, we can re-apply the first phase to the modified instance to construct
a suitable integer vector r such that (c, c, r, r) is realizable. After switching
back the roles of U and V , we gain a bi-graphical pair (r, c) of integer vectors.
Afterwards, a realization is constructed by Ryser’s algorithm.
Example

We start where the first phase stopped.

r̃ = (4, 1, 0)

r̄ = (4, 2, 3)

c = (2, 2, 1, 1, 0)

c0 = (4, 2, 0)

Σr̃ = (4, 5, 5)

Σr̄ = (4, 6, 9)

Σc = (2, 4, 5, 6, 6)

Σc0 = (4, 6, 6).

6

Algorithm 2: Phase Two
Input: realizable four-tuple (r̃, r̄, c, c)
Output: bi-graphical pair (r, c)
1 r ← r̃
// initialize r with lower bounds r̃
n
n
// calculate number of steps
2 δ2 ← Σc 2 − Σr̃ 1
3 i ← n1
// right-most position such that r̃i < r̄i
4 for k = 1, 2, . . . , δ2 do
5
while ri = r̄i do
// proceed to next position with ri < r̄i
6
i←i−1
7
end
8
j ← min{` : r` = ri }
// identify left-most rj with rj = ri
9
swap r̄i and r̄j
10
rj ← rj + 1
11 end
12 return (r, c)

v1

u1

u2

u3

v2

v3

v4

v5

Figure 1: Realization of the sequence pair r = (4, 1, 1), c = (2, 2, 1, 1, 0).
The number of iterations is determined by δ2 ← 6 − 5 = 1.
1. The inner loop breaks with i = 3. The left-most component equal to r3 = 0
is at position j = 3. Thus, the algorithm switches r̄3 and r̄3 and increments r3 . We gain r = (4, 1, 1) and r̄ = (4, 2, 3).
The situation at the end of the second phase:
r = (4, 1, 1)

c = (2, 2, 1, 1, 0)

c0 = (4, 2, 0)

Σr = (4, 5, 6)

Σc = (2, 4, 5, 6, 6)

Σc0 = (4, 6, 6)

We verify by Theorem 1 that (r, c) is bi-graphical. Fig. 1 shows a realization.
Proof of Correctness The correctness of the second phase can be shown
very similarly to phase one and follows directly from the following theorem.
Lemma 5. Let r(k) and r̄(k) be the state of the integer vectors r and r̄ after
exactly k iterations of the outer loop in Alg. 2. Then, (r(k) , r(k) , c, c) is realizable
if and only if k = δ2 = Σnc 2 − Σnr̃ 1 .
Proof. By Theorem 2, the four-tuple (r(k) , r(k) , c, c) is realizable if and only
1
if r(k) ≤ c0 and c E (r(k) )0 hold. In particular, Σnr(k)
= Σnc 2 must hold.
7

1
Since Σnr̃(k)
6= Σnc 2 for k 6= Σnc 2 − Σnr̃ 1 , the four-tuple (r̃(k) , r̃(k) , c, c) cannot be realizable if k 6= δ2 . On the other hand, as (r(k) , r̄(k) , c, c) is realizable and thus r(k) E c0 holds after each iteration by Lemma 3, the four1
tuple (r(k) , r(k) , c, c) will be realizable as soon as Σnr(k)
= Σnc 2 holds, which is
true after exactly δ2 iterations.

Running Time By similar arguments as before, the running time of the
second phase can be described by O(n1 + n2 + Σnc 2 ). As Ryser’s algorithm
produces a realization G = (U, V, E) of the bi-graphical pair (r, c) in O(|U | +
|V | + |E|) time and |E| = Σnc 2 ≥ Σnr̃ 1 , the total running time of the realization
algorithm is O(|U | + |V | + |E|). Since we cannot hope to construct a bipartite
graph in sub-linear time, our algorithm is asymptotically optimal.

3.3

Edge-Minimality

Lemma 6. The bipartite graph produced by our algorithm is edge-minimal.
Proof. Let (r, c) be a bi-graphical pair of integer vectors associated to an arbitrary realization G = (U, V, E) of the four-tuple (r̃, r̄, c̃, c̄). As c̃ ≤ c must hold,
the number of edges |E| is bounded from below by |E| ≥ Σc̃n2 . In addition,
if (r, c) is bi-graphical, the four-tuple (r̃, r̄, c, c) must be realizable. Hence, the
inequalities Σjr̃ ≤ Σjc0 = Σjc̃0 + xj must hold for each j in range 1 ≤ j ≤ n1 .
Thus, xj = Σjr̃ − Σjc̃0 is the minimal number of edges that G needs to possess in
addition to the Σnc̃ 2 edges, so that the inequality Σjr̃ ≤ Σjc0 can hold. Hence, the
total number of edges is bounded from below by |E| ≥ Σnc̃ 2 + max{xj : 1 ≤ j ≤
n2 } = Σnc̃ 2 + δ1 . Since our algorithm produces a bipartite graph G = (U, V, E)
with exactly |E| = Σnc̃ 2 + δ1 edges, G is edge-minimal.
Remark Our algorithm can easily be used to construct edge-maximal realizations. For this purpose, consider an arbitrary edge-minimal realization G =
(U, V, E) of the four-tuple (r̃, r̄, c̃, c̄). The associated complement graph G∗ =
(U, V, E ∗ ) is defined by E ∗ = (U × V ) \ E. By construction, the graph G is
edge-minimal if and only if G∗ is edge-maximal. In addition, it follows from
definition that the degrees of G∗ are bounded from below and above by the
complementary four-tuple (r̃∗ , r̄∗ , c̃∗ , c̄∗ ) with
r̃∗ = (n2 − r̄1 , n2 − r̄2 , . . . , n2 − r̄n1 )
r̄∗ = (n2 − r̃1 , n2 − r̃2 , . . . , n2 − r̃n1 )
c̃∗ = (n1 − c̄1 , n1 − c̄2 , . . . , n1 − c̄n2 )
c̄∗ = (n1 − c̃1 , n1 − c̃2 , . . . , n1 − c̃n2 ).
Thus, we can find an edge-maximal realization by first determining an edgeminimal realization of the complementary four-tuple (r̃∗ , r̄∗ , c̃∗ , c̄∗ ) and creating
the associated complement graph.

8

4

Conclusion

We gave a description of an algorithm that constructs a bipartite graph G =
(U, V, E) whose degrees lie in prescribed intervals and showed that this algorithm
has a running time of O(|U | + |V | + |E|). Since this is asymptotically optimal,
the algorithm can be used to efficiently solve the realization problem.

Acknowledgements
We thank Matthias Müller-Hannemann and Annabell Berger for their valuable
suggestions and detailed remarks. This research did not receive any specific
grant from funding agencies in the public, commercial, or not-for-profit sectors.

References
[1] R. P. Anstee. An algorithmic proof of Tutte’s f-factor theorem. Journal of
Algorithms, 6(1):112–131, 1985.
[2] D. R. Fulkerson. A network flow feasibility theorem and combinatorial applications. Can. J. Math, 11:440–451, 1959.
[3] D. Gale. A theorem on flows in networks. Pacific J. Math., 7(2):1073–1082,
1957.
[4] James B Orlin. Max flows in O (nm) time, or better. In Proceedings of the
forty-fifth annual ACM symposium on Theory of computing, pages 765–774.
ACM, 2013.
[5] S. Rechner, L. Strowick, and M. Müller-Hannemann. Uniform Sampling of
Bipartite Graphs with Degrees in Prescribed Intervals. submitted to Journal
of Complex Networks.
[6] Herbert J Ryser. Combinatorial properties of matrices of zeros and ones.
Canadian Journal of Mathematics, 9:371–377, 1957.
[7] M. Schocker. On graphs with degrees in prescribed intervals. In Algebraic
Combinatorics and Applications, pages 307–315. Springer, 2001.

9

