On the Enumeration of Bipartite Minimum Edge
Colorings
Yasuko MATSUI and Takeaki UNO
Abstract. For a bipartite graph G = (V, E), an edge coloring of G is a coloring of the edges of G such that any two adjacent edges are colored in different colors. In this paper, we consider the problem of enumerating all edge
colorings with the fewest number of colors. We propose a simple polynomial delay algorithm whose amortized time complexity is O(|V |) per output,
whereas the previous fastest algorithm took O(|E| log |V |) time per output.
Although the delay of the algorithm is O(|E||V |), the delay of our algorithm
can be reduced to O(|V |) by using a simple modification with a queue ofpolynomial size. We show an improvement to reduce the space complexity from O(|V ||E|) to O(|E| + |V |). Furthermore, we obtain a lower bound(|E| − |V̂ | + 1) max{2∆−3 , 2(|V̂ |/2 + 1)∆−3 /(∆ − 1)}/∆ of the number of edge
colorings included in G, where ∆ is the maximum degree and V̂ is the set ofvertices of the maximum degree.

Keywords : enumeration, generation, listing, edge coloring, bipartite graph, algorithm, complexity, output polynomial.

1. Introduction
Enumeration problems and enumeration algorithms are quite fundamental in computer science. The subject has a long history, and many studies have been done
[5, 7, 9, 14, 16, 18]. Enumeration has many applications in the other area of computer science, such as optimization, sampling, data mining, bioinformatics, and soon. For example, the basis of branch and bound algorithms is the enumeration,and many exact algorithms for NP-hard problems, which are actively studied inthese 10 years, use enumeration algorithms. In data mining, the pattern mining algorithms, which finds all the patterns satisfying given constraints from a database,utilize the enumeration of candidate patterns[1]. Particularly, the recent increaseof the power of computers supports the efficiency of enumeration approaches inpractice.

2

Yasuko MATSUI and Takeaki UNO

A weak point of enumeration approach is that there are quite few generalized
problems which contain many other enumeration problems as their special cases.
For example, in optimization, linear programming is a generalized problem, andit includes many other problems as its special cases, such as maximum matchings,
network flow problems, assignment problems. In contrast, only few enumeration
problems can be efficiently solved by other enumeration algorithms. For example,
if we enumerate all spanning trees in a given graph G by enumerating all subtreesof G, it possibly takes exponential time for each spanning tree, since the numberof subtrees is often exponentially larger than the number of spanning trees. If wewant to reduce an enumeration problem A to an enumeration problem B, we haveto preserve the structures with respect to all the solutions. In contrast to it, in
optimization problems, we have to preserve only structures with respect to optimal
solutions. Intuitively, this is one of difficulties of the reduction on enumeration
problems.
One approach to handle enumeration problems efficiently is to develop fundamental techniques commonly applicable to many enumeration problems. For
achieving polynomial algorithms, there are several techniques, such as divide andconquer (binary partition), backtracking, and reverse search. Here an enumeration algorithm is polynomial time if the computation time is polynomial in the
input size and the output size of the input problem. For reducing the order of
the time complexity of polynomial time algorithms, such as using the sparsity,
data structures, and amortized analysis of the time complexity. There are quite
many kinds of enumeration problems, thus it is important to develop and summarize efficient techniques. One of the big tasks in the research of enumeration
algorithms is to clarify what kind of structures of the problems help to reduce thetime complexity, and what kind of techniques can be applicable to the structures.
In the literatures, we can see many efficient but simple enumeration algorithms
for fundamental graph objects such as paths and cycles[11], spanning trees[7, 16],
independent sets and cliques[6], and matchings[4], and fundamental geometicalobjects such as vertices of polytopes[2], non-crossing spanning trees in plane[2],and floorplans[14].
In this paper, we consider the problem of enumerating all the minimum edge
colorings of a given bipartite graph with multiple edges. Let G = (V (= V1 ∪V2 ), E)
be a bipartite graph with vertex set V and edge set E. An edge coloring of G isa coloring of all the edges of G such that no pair of adjacent edges is colored thesame. An edge coloring with the minimum number of colors is called a minimumedge coloring. We simply denote a minimum edge coloring by an edge coloring if
there is no confusion. We denote the maximum degree of G by ∆(G), and the setof vertices of maximum degree by V̂ (G). If there is no confusion, we simply write
them ∆ and V̂ .
In 1916, König [8] proved that any minimum edge coloring of a bipartite
graph G uses exactly ∆ colors. Since no edges with the same color are adjacent,the set of edges with the same color forms a matching. Hence we can considerOn the Enumeration of Bipartite Minimum Edge Colorings

3

an edge coloring as a partition of E into ∆ disjoint matchings. The enumeration
problem of edge coloring considered here is to output all the ways of partitioningof E into disjoint ∆ matchings.
An algorithm for solving the problem has been proposed by Matsui andMatsui [12, 13]. The amortized time complexity of the algorithm is O(|E| log |V |)per edge coloring, and the space complexity is O(∆|E|). The current best timecomplexity algorithm for finding a minimum edge coloring in a given bipartite
graph, which is proposed by Cole, et al., and Schrijver [3, 15], takes O(|E| log |V |)time, hence naturally we may think that Θ(|E| log |V |) is a kind of lower bound forthe time complexity. However, the structure of the set of edge coloring seems tohave an advantage. For any edge coloring, we can generate another edge coloringby exchanging several edges of two matchings in it, along an alternating cycle. Thisimplies that when we traverse the set of edge colorings, we basically need the time
to exchange the edges along a cycle, which seems to be very short in average. Thus,
naturally there is a question “Is there an algorithm for enumerating all minimumedge colorings in short time for each”.
In this paper, we give a positive answer to the question. We propose a simple
algorithm running in O(|V |) time for each edge coloring. The space complexity is also reduced to O(|E| + |V |). In detail, the delay[6] of the algorithm isO(∆|E| log |V |). The delay is the maximum computation time between two consecutive output. Actually, by the technique described in [17], we can reduce thedelay to O(|V |) by using O(∆|E|) extra memory. We note that to output an edge
coloring, our algorithm outputs the symmetric difference between an edge coloring
and the next one instead of exact output. It reduces the computation time for
output one edge coloring to O(|V |) on average.
The main technique to reduce the time complexity is on the analysis of
the time complexity. Actually, our algorithm is obtained by adding slight andsimple modifications to the previous algorithm. It uses neither complicated data
structures nor sophisticated algorithms. The modifications of the algorithm avoid
the worst cases which make the time complexity of the previous algorithm tight.
It is interesting that such kind of simple modifications reduces the time complexity so much. This is also an advantage from both theoretical and application viewpoints. Furthermore, as a corollary of the amortized analysis, we give(|E| − |V̂ | + 1) max{2∆−3 , 2(|V̂ |/2 + 1)∆−3 /(∆ − 1)}/∆ as a lower bound of thenumber of edge colorings included in G.
The organization of this paper is as follows. We explain the framework of ourenumeration algorithm in Section 2. In Section 3, we analyze the time complexity,
and show a lower bound of the number of edge colorings included in a graph.
Finally, we explain a way to reduce the space complexity in Section 4.

4

Yasuko MATSUI and Takeaki UNO

Figure 1. An example of enumeration of edge colorings. Eachcircle denotes a problem/subproblem, and arrows connect problems and their subproblems. Each arrow corresponds to a covering
matching which is obtained from each subproblem.

2. Framework of Algorithm for Enumerating Edge Coloring
The basis of our enumeration algorithm is the same as that described in [12, 13].
We start the explanations with the definitions and properties. For a vertex set W,
a matching covering all the vertices of W is called a covering matching for W. If
no confusion can arise we will omit W . From König’s theorem, any minimum edge
coloring uses exactly ∆ colors. This means that any vertex of V̂ is incident toedges with all colors, and any matching which forms a minimum edge coloring is acovering matching for V̂ . Conversely, any covering matching M for V̂ is included
in at least one minimum edge coloring, since the removal of M from G is a graphwith maximum degree ∆ − 1.
For an edge e, any edge coloring includes just one covering matching including
e. Thus, edge colorings of G is partitioned into groups by the covering matchings
including e. This observation immediately leads to the following algorithm.
ALGORITHM: Basic Algorithm (G = (V, E), C)(BA1) If G is a matching then output C(BA2) e := an edge of G
(BA3) For each covering matching M for V̂ including e
Call Basic Algorithm((V, E \ M ), C ∪ {M })On the Enumeration of Bipartite Minimum Edge Colorings

5

V1
s
V2

Figure 2. An instance of D1 (G, M, W ) : Gray vertices are in W,
and bold edges are in matching M.

Figure 1 shows an example of the execution of the algorithm. The enumeration of covering matchings in (BA3) can be done by using an algorithm proposedin [12, 13]. We explain their algorithm next. For conciseness, we modify theiralgorithm slightly.
For an edge e = (u, v), let G\e = (V, E \{e}), and G−{u, v} be the subgraphof G obtained by removing u, v, and all edges incident to either u or v. Here we
consider the set of covering matchings for a vertex set W . Then, we can see thatthe set of the covering matchings not including e is equal to the set of covering
matchings in G \ e. Similarly, we can see that the set of the covering matchings
for W \ {u, v} including e is equal to the set of matchings obtained by adding e
to each covering matchings in G − {u, v}. Thus, this enumeration problem can bepartitioned into two subproblems.
To partition the problem, we choose an edge e from the symmetric difference
between two covering matchings M and M 0 . This ensures that both subproblems
are non-empty, since either M or M 0 includes e. By augmenting the matching, we
can find a covering matching which covers vertices in V̂ We thus explain how tofind a covering matching different from the given covering matching.
For the explanation, we define the following notation. Let Z be the set of
isolated vertices in G. We recall that V1 and V2 are the partition of V so that G
is a bipartite graph.
Ū1 is the set of vertices in V1 \ (Z ∪ W ) incident to an edge of M.
Ū2 is the set of vertices in V2 \ (Z ∪ W ) incident to an edge of M.
U1 is the set of vertices in V1 \ (Z ∪ W ) incident to no edge of M.
U2 is the set of vertices in V2 \ (Z ∪ W ) incident to no edge of M.
Let D1 = (G, M, W ) be the directed graph obtained from G as follows:
1. remove all isolated vertices from G
2. orient the edges of M from V1 to V2 , and the edges of E \ M from V2 to V1
3. add a vertex s to V
4. add the arcs from s to each vertex of Ū1 ∪ U2 , and6

Yasuko MATSUI and Takeaki UNO
5. add the arcs from each vertex of Ū2 ∪ U1 to s.

For an example of D1 (G, M, W ), see Figure 2. For a directed cycle C of D1 (G, M, W ),we define E(C) by the set of all edges corresponding to the arcs of C. From the ruleof orienting edges, edges of M and edges not in M appear in E(C) alternatively
in any directed cycle. This is a common technique to find alternating paths andalternating cycles.
D1 (G, M, W ) is equivalent to the graph obtained by contracting the sourceand sink of the graph G0 (G, M ) used in the find-matching algorithm of [13]. In[13], the following lemma is proved.
Lemma 1. [13] The following two conditions hold.
(1) For any directed cycle C of D1 (G, M, W ), M 4E(C) is a covering matchingfor V̂ .
(2) If D1 (G, M, W ) has no directed cycle, then M is the unique covering matchingof G.

Since [13] is not a journal paper, we include a proof here.
Proof. For any two covering matchings M and M 0 , the symmetric difference between them is composed of paths and cycles. Any cycle of those cycles forms a
directed cycle in D1 (G, M, W ). Any path P of those paths forms a directed path
P 0 of D1 (G, M, W ) whose end vertices are not in W. Moreover, since the end edgesof P are not adjacent to the edges of M, one end vertex of P is in Ū1 ∪ U2 and theother is in Ū2 ∪ U1 . Hence, by connecting s and the end vertices of P 0 , we obtaina directed cycle.
Let C be a directed cycle of D1 (G, M, W ). If C does not include s, thenM 4E(C) is a covering matching, since the sets of vertices incident to the edgesof matchings are the same for M and M 4E(C). If C includes s, then E(C) is apath connecting a vertex of Ū1 ∪ U2 and a vertex of Ū2 ∪ U1 . Hence, M 4E(C) isa matching. Since the end vertices of E(C) are not in W, M 4E(C) is a covering
matching.

A covering matching for V̂ can be found in O(|E| log |V |) time by the algorithms of Cole et al., and Schrijver [3, 15]. Actually, the computation time can bealso bounded by O(|V̂ |2 ∆), by removing all the edges incident to no vertex of V̂ in
O(|E|) time. Thus, the enumeration of covering matchings takes O(|E| + |V̂ |2 ∆)time for the first covering matching, and O(|E|) for each following covering matching.
Our algorithm is obtained by introducing three additional modifications tothe basic algorithm. These modifications are the following. We note that a star isa graph such that all the edges are incident to a vertex.
(1) if the input graph is a star, then output the unique edge coloring directly(2) choose an edge incident to not all the edges in (BA2)(3) output by the difference from the previous output

On the Enumeration of Bipartite Minimum Edge Colorings

7

The modified algorithm is described below. Note that the algorithm is composed of two procedures, the main part and the enumeration of covering matchings.
The procedures are nested so that they call recursively each other. The algorithm
memorize a graph with multiple edges by its underline graph with the multiplicity
for each edge. Hence, the memory space never exceed O(|V |2 ). For outputting anedge coloring of a star, we output its underline graph and the multiplicities, and amessage ”each edge is a matching”, instead of exact output. By this modification,
the execution of (1) never take more than O(|V |) time. In the next section weanalyze the time complexity of the algorithm to bound it by O(|V |) for each.
ALGORITHM: Enum Edge Coloring(G = (V, E):graph,
Col:set of matchings to be edge colorings)(1) If ∆(G) = 1, output edge coloring Col ∪ {E}(2) If (G is a star) or (E is a matching) then output Col and the unique edge
coloring of G// improvement (1)(3) (u, v) := an edge not adjacent to all edges // improvement (2)(4) M := a covering matching for V̂ (G) of G including e// computed in O(|V̂ |2 ∆) time(5) Call Enum Covering Matching (G − {u, v}, V̂ (G) \ {u, v}, M \ {(u, v)}, G, Col)// enumerate covering matchings
ALGORITHM: Enum Covering Matching(H:graph, W :vertices to be covered,M :edge set to be a matching, G:original graph,
Col:set of matching to be an edge coloring)(6) If no directed cycle is in D1 (H, M, W ) thenCall Enum Edge Coloring ((V, E \ M , Col ∪ {M } )// generate recursive call when a new covering matching is found(7) C := a directed cycle of D1 (H, M, W ) ; M 0 := M 4E(C) ;(u, v) := an edge in M 4M 0(8) If (u, v) ∈ M 0 then swap M and M 0// now (u, v) is an edge in M \ M 0(9) Call Enum Covering Matching (H − {u, v}), W \ {u, v}, M \ {(u, v)}, G, Col)// enumerate covering matchings including (u, v)(10) Call Enum Covering Matching (H \ (u, v), W, M 0 , G, Col)// enumerate covering matchings not including (u, v)

3. Analysis of the Time Complexity
In this section, we now start with some definitions. We define an iteration of
the enumeration algorithm of edge colorings by the set of operations to generate
subproblems for enumerating edge colorings from an input graph, i.e. the union of
the iteration of Enum Edge Coloring inputing graph G and all the iterationsof8

Yasuko MATSUI and Takeaki UNO

Enum Covering Matching which enumerate covering matchings of G. For each
iteration x, we denote the input graph of x by Gx = (V, Ex ). Iterations generated
by x are called the children of x. The depth of the recursion is up to ∆, and each
iteration on the bottom of the recursion outputs an edge coloring.
Lemma 2. For a graph G with ∆ ≥ 3, a covering matching for V̂ including anedge e = (u, v) is unique if and only if all edges of G are adjacent to e.
Proof. The ‘if’ part is obvious, thus we prove the ‘only if’ part by its contraposition.
Let M be a covering matching for V̂ . We show that D1 (G − {u, v}, M, V̂ \ {u, v})
includes a directed cycle. From Lemma 1, this implies that G has a covering
matching different from M. Since at least one edge is not adjacent to e, G − {u, v}
contains at least one edge. For any vertex w of V̂ \ {u, v}, w is incident to at mostone of u and v. Hence, its degree in G − {u, v} is no less than two, and w has
at least one out-going arc in D1 (G − {u, v}, M, V̂ \ {u, v}). For any vertex w inV \ V̂ \ {u, v}, there is an arc (w, s) or (w, x) for some x 6= u, v since (w, x) in M.
Hence the out-degree of any non-isolated vertex of D1 (G − {u, v}, M, V̂ \ {u, v}) isat least one. Therefore, a depth-first search for the graph always reaches a vertex
that has already been visited, and gives a directed cycle.

If any edge of Gx is adjacent to all the other edges, then all the edges are
incident to a vertex (note that Gx is bipartite), and Gx is a star. In this case thealgorithm outputs the unique edge coloring in (1) and the iteration terminates, inO(|V |) time. In the other case, the algorithm chooses an edge e so that at least
one edge is not adjacent to e. From Lemma 2, at least two covering matchings
includes e. Thus, we have the following corollary.
Corollary 1. In algorithm Enum Edge Coloring, if an iteration has a child, thenumber of its children is at least two.
This corollary implies that the number of vertices in the enumeration tree
is at most twice the number of leaves, which is the same as the number of edge
colorings in G. To bound the number of iterations more, we give the following
lemmas, where the first one is a standard result of graph theory.
Lemma 3. For a directed graph H = (VH , AH ) in which each arc is included ina directed cycle, H contains at least |AH | − |VH | + cc(H) directed cycles, where
cc(H) is the number of strongly connected components of H.
Proof. If all the arcs are self-loops or |VH | = 1, the statement holds. Assume thatthe statement holds if |VH | < k, and we consider the case that |VH | = k andnot all arcs of H are self-loops. Let C be a shortest directed cycle of H including
no self-loop, and |C| denote the number of arcs in C. Note that |C| ≥ 2. Let
H 0 = (VH 0 , AH 0 ) be the graph obtained from H by removing all the arcs of C andcontracting vertices of C into a vertex. Since |VH 0 | = |VH | − |C| + 1 < k, H 0 has
at least|AH 0 | − |VH 0 | + cc(H 0 ) = (|AH | − |C|) − (|VH | − |C| + 1) + cc(H)On the Enumeration of Bipartite Minimum Edge Colorings

9

directed cycles. Note that cc(H) = cc(H 0 ). Since H has at least one more directed
cycle (which is C) than H 0 , H has at least(|AH | − |C|) − (|VH | − |C| + 1) + cc(H) + 1 = |AH | − |VH | + cc(H)directed cycles.



Theorem 1. Any graph G with ∆ ≥ 3 and |V̂ | ≥ 3 has at least (|E| − |V̂ | +1) max{2∆−3 , 2(|V̂ |/2 + 1)∆−3 /(∆ − 1)}/∆ edge colorings.
Proof. Let Z be the set of isolated vertices in G, and M be a covering matching. In
D1 (G, M, V̂ ), any non-isolated vertex not in V̂ is connected to s, hence its degree
is at least 2, and the degree of s is |V | − |Z| − |V̂ |. Therefore, the number of arcs
in D1 (G, M, V̂ ) is at least |E| + (|V | − |Z| − |V̂ |). For any edge e, an edge coloringof G includes both a covering matching which includes e and another covering
matching which does not. This means that any arc of D1 (G, M, V̂ ) is included ina directed cycle. From Lemma 3, D1 (G, M, V̂ ) includes at least|E| + (|V | − |Z| − |V̂ |) − (|V | + 1) + |Z| + 1 = |E| − |V̂ |directed cycles. Thus, G includes at least |E| − |V̂ | + 1 covering matchings.
Let v be a vertex in V̂ and F be the set of edges incident to v. Any covering
matching includes an edge in F , hence there is an edge f in F such that f isincluded in at least (|E| − |V̂ | + 1)/∆ covering matchings. Thus, if ∆ = 3, G
includes at least (|E| − |V̂ | + 1)/3 edge colorings.
We next consider the case ∆ > 3. Similar to the above, for any covering
matching M , the graph H = (V, E \M ) includes at least (|E \M |−|V̂ |+1)/(∆−1)
covering matchings including an edge f , which is incident to a vertex in V̂ (H).
Since |E| ≥ ∆|V̂ |/2), we have(|E \ M | − |V̂ | + 1)/(∆ − 1) ≥ ((∆ − 3)|V̂ (H)|/2 + 1)/(∆ − 1).
From Lemma 3, if |V̂ | ≥ 3, there is an edge f incident to a vertex in V̂ (H) included
in at least two covering matchings. Therefore, by induction, G has at least((|E| − |V̂ | + 1)/∆) ×∆−1
Y

max{2, ((i − 1)|V̂ |/2 + 1)/i)

i=3
∆−3

≥ (|E| − |V̂ | + 1) max{2, 2(|V̂ |/2 + 1)∆−3 /(∆ − 1)}/∆edge colorings.
In particular, we can directly obtain the following corollary from the fact that|E| ≥ ∆|V̂ |/2.
Corollary 2. Any graph G with ∆ = 3 has at least |V̂ |/6 edge colorings.
From these lemmas and corollary, we obtain the following theorem.
Theorem 2. The algorithm Enum Edge Coloring enumerates all minimum edge
colorings of a bipartite graph G = (V, E) with multiple edges in O(|V |N ) time,
where N is the number of minimum edge colorings of G.

10Yasuko MATSUI and Takeaki UNO

Proof. For any child y obtained at iteration x, we have |Ey | ≥ |Ex | − |V |/2, since
Ey is obtained by removing a matching from Ex . An iteration x takes O(|Ex | +|V | + |V̂ (Gx )|2 ∆(Gx )) time and O(|Ex | + |V |) time per child. By assigning acomputation cost of O(|Ex | + |V |) to each child, we suppose that the computation
time T (x) of x is
c × |V |if ∆(Gx ) < 3 or Gx is a star
T (x) =.
2c × (|V̂ (Gx )| ∆(Gx ) + |Ex | + |V |) otherwise
Here c is a constant, and T (x) does not include the computation time for outputting the edge colorings. We have |V̂ (Gx )| ≤ |V̂ (Gy )|, since any vertex of V̂ (Gx )is the maximum degree in Gy . Hence, if ∆(Gx ) > 3 and Gx is not a star,
T (x) =c × (|V̂ (Gx )|2 ∆(Gx ) + |Ex | + |V |)≤ c × (|V̂ (Gy )|2 (∆(Gy ) + 1) + |Ey | + 1.5|V |).
Hence, from Corollary 1, for any 4 ≤ k ≤ ∆(G),
X
T (x)x|∆(Gx )=k,Gx is not a starX≤c × (|V̂ (Gy )|2 (∆(Gy ) + 1) + |Ey | + 1.5|V |)/2
y|∆(Gy )=k−1≤

X

3T (y)/4.

y|∆(Gy )=k−1

Therefore, from Lemma 2,
X

T (x) ≤x|∆(Gx )≥3X

4T (x)x|∆(Gx )=3≤X

48c(|V̂ (Gx )||V |)x|∆(Gx )=3≤ 48cN |V |Next we consider the computation time for outputting the obtained edge
colorings. Consider the recursive structure of our algorithm as a recursion tree.
Our algorithm outputs the difference from the edge coloring output just before.
From the edge coloring which is outputted just before, the size of the difference
is at most |V |/2 times the number of edges in the recursion tree traced by thealgorithm. Hence, the sum of these numbers of edges in the output is at most|V |/2 × 2(# of iterations). Since the number of iterations is less than 2N, thecomputation time for output is O(|V |N ) per output. We note that the algorithm
outputs the unique edge coloring in a star in O(|V |) time.
On the Enumeration of Bipartite Minimum Edge Colorings

11

4. Reducing Delay
The delay is the maximum computation time between two consecutive outputs.
An enumeration algorithm is said to be polynomial delay if its delay is polynomialof the input size[6]. If an enumeration algorithm is polynomial delay, it is output
polynomial time, but an output polynomial time algorithm is not always polynomial delay. Thus, polynomial delay is a stronger result than output polynomial.
We recall that an enumeration algorithm is output polynomial if the computation
time is bounded by a polynomial of the input and output size. In this section, we
carefully analyze the delay of our algorithm.
First, we show that the delay of covering matchings enumeration can bebounded by O(|E|). In [10, 17], they claimed that if an enumeration algorithm
outputs a solution in each iteration, then the delay can be 3 times the maximum
computation time of an iteration. Algorithm Enum Covering Matching finds
a new matching in each iteration, thus we can modify the algorithm to satisfy thecondition. The idea in [10, 17] is to modify the algorithm so that the algorithm
outputs a solution before executing recursive calls at odd levels of the recursion,and after the recursive calls at even levels. Then, we can see that at least one
iteration of any consecutive three iterations must output a solution. Thus, delayis O(|E|) without increasing neither time nor space complexity.
Next, we reduce the delay of the main algorithm. For an iteration I of an
enumeration algorithm, let Out(I) be the set of solutions output by the iterations
which are descendants of I. Suppose that the delay of an enumeration algorithm
A is D, and satisfies that for any iteration I, the amortized computation time
taken by all descendants of I is T per solution in Out(I). In [17], we can see that
under these conditions, the delay can be reduced to O(T ) with using O(D/T × S)
memory where S is the maximum size of output. The main idea is that we makea buffer and insert each solution into the buffer when the algorithm outputs it.
The solutions in the buffer is extracted and output one by one with keeping theintermediate computation time equal to 6T unless the buffer is overflow. We canprove that after the buffer is once full, it never be empty. At the beginning of theenumeration, we do not extract solutions from the buffer until the first overflowof the buffer. Then, the delay is 6T = O(T ).
On our algorithm, T = O(|V |) and S = |V |. Since each iteration of bothprocedures takes O(|E|) time, and the depth of the recursion is O(∆), the delayis O(∆|E|). According to the above, we can reduce the delay to O(|V |) by using
O(∆|E|) memory.

Theorem 3. Minimum edge colorings in a bipartite graph G = (V, E) can be enumerated in O(|V |) delay by using O(∆|E|) memory, where ∆ is the maximum
degree in G.

12

Yasuko MATSUI and Takeaki UNO

8

3

2

5

9
7

1

10

6
4

8

9
7

10

4

Figure 3. An example of G and G(I ∪ M, l). In the figure, theedges of I ∪ M are shown by the bold lines, and l = 6.

5. Reducing Space Complexity
In this section, we describe a way for reducing the space complexity. Since ourenumeration algorithm is composed of two nested enumeration algorithms, which
are for edge colorings and for covering matchings, the total depth of two recursions can be up to Θ(∆|E|). Note that here the iterations are different from thedefinition in Section 3. Here we consider that an iteration is the computation timein a recursive call except for the computation done in the further recursive calls
generated in it.
Each recursive call requires Ω(1) memory, hence the total required memory
is up to Θ(∆|E|). When Enum Covering Matching generates a subroutine callof Enum Covering Matching, O(|E| + |V |) memory is required to store H ineach level, hence the accumulated memory for storing H is up to O(∆(|E| + |V |)).
These two parts are the bottle neck of the space complexity. Note that the total
accumulated memory to store M and I is O(|E|), since each time the algorithm
executes, stored matchings M ∪ I compose a subset of an edge coloring. Note alsothat V̂ can be computed from V̂ and I in O(|E| + |V |) time.
To improve these memory-consuming parts, we add the following two modifications to Enum Covering Matching. The first one is to use a loop instead ofgenerating a recursive call with respect to H \ e. By this modification, a recursive
call always adds an edge to I or a matching to C, hence the depth of the recursion
is at most |E| + |V |.
The second modification is to use the minimum possible index edge e to partition the problem, in Enum Covering Matching. For a graph G, a matchingM, and an index j, let G(M, j) = (V, X) whereX = {ei ∈ E|i ≥ j and (ei is not adjacent to any edgeeh ∈ M, h < j}

On the Enumeration of Bipartite Minimum Edge Colorings

13

For an example of G(M, j), see Figure 3.
Suppose that an iteration of Enum Covering Matching inputs a graph H
and a covering matching M . Let el be the minimum index edge of H. If el ∈ E(C)for a directed cycle C of D1 (H, M, V̂ ), the condition holds for both subproblems
generated by el . If el 6∈ E(C) for any directed cycle C of D1 (H, M, V̂ ), the condition holds for H and G(I ∪ M, l). Therefore, by induction, at any iteration ofEnum Covering Matching inputting H, V̂ , M, and I such that the minimum
index edge of H is el , the set of covering matchings in H and that of G(I ∪ M, l)
are equal. From this, we can see that a graph equivalent to H can be constructedfrom G, I ∪ M, l in O(|E| + |V |) time.
By using these two modifications, the space complexity is reduced to O(|E| +|V |). We now describe the algorithm with these two modifications.
ALGORITHM: Enum Covering Matching2 (H, M, V̂ )(1) If D1 (H, M, V̂ ) includes no directed cycle then output M ; return(2) el (= (ul , vl )) := the minimum index edge of H included in some directed cycle(3) H := G(M, l) // remove edges less than l and not included in M
(4) C := a directed cycle including el ; M 0 := M 4E(C)(5) If el ∈ M then swap M and M 0(6) Call Enum Covering Matching2 (H − {ul , vl }, M 0 ∪ {(ul , vl )}, V̂ \ {ul , vl })// H will be changed by the execution of the recursive call(7) H := G(M, l)(8) Remove el from H ; go to (1)Step (1) outputs a covering matching if the covering matching of H is unique.
An execution of (2) through (8) corresponds to an internal iteration which has somechildren in the enumeration tree. el is the edge to be used partitioning the problem,
step (6) generates a recursive call for enumerating covering matchings including el ,and step (8) corresponds to the recursive call for enumerating covering matchings
not including el . Setting H to G(M, l) in (3) is equivalent to removing the edges
whose indices are less than l and not included in M . Since the recursive call in (6)changes H, H is not preserved after the termination of the recursive call. However,
G is preserved in the execution1 , we can reconstruct H by setting H to G(M, l).
This is the key to save the memory for storing H during the execution of therecursive call. Step (8) removes el from H and go to the beginning. It corresponds
to the recursive call for enumerating covering matchings not including el .
By using this algorithm, we obtain the following theorem.
Theorem 4. The algorithm Enum Edge Coloring with Enum Covering Matching2
enumerates all minimum edge colorings of a bipartite graph G = (V, E) with multiple edges in O(|V |N ) time and O(|E| + |V |) space, where N is the number ofminimum edge colorings of G.

1 In exact, G is changed by recursively calling Enum Edge Coloring, however it is reconstructed
after the termination by adding the covering matching which is removed before the execution

14

Yasuko MATSUI and Takeaki UNO

6. Conclusion
We proposed an algorithm for enumerating all minimum edge colorings in a bipartite graph G = (V, E) without using any sophisticated data structure or any
sophisticated algorithm. The amortized time complexity of the algorithm is O(|V |)per output. It improves the previous algorithm by a factor of |E| log |V |/|V |. We
also reduced the space complexity of the algorithm from O(|E|∆) to O(|E| + |V |).
Although the delay of the algorithm is O(∆|E|), we can reduce it to O(|V |) byusing a queue with O(∆|E|) memory. We further give a lower bound (|E| − |V̂ | +1) max{2∆−3 , 2(|V̂ |/2 + 1)∆−3 /(∆ − 1)}/∆ of the number of edge colorings included in G.

Acknowledgments
We would like to thank Professor Akihisa Tamura of Kyoto University andProfessor Yoshiko T. Ikebe of Tokyo University of Science for their advice, andProfessor David Avis of McGill University for his careful reading of our paper. This
research is supported by Grant-in-Aid for scientific research from the ministry ofeducation, science, sports and culture of Japan.

References[1] R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo, “Fast Discovery
of Association Rules,” Advances in Knowledge Discovery and Data Mining, MIT
Press (1996), pp. 307–328, .
[2] D. Avis and K. Fukuda, “Reverse search for enumeration,” Discrete Applied Mathematics, 65 (1996), pp. 21–46.
[3] R. Cole, K. Ost and S. Schirra, “Edge-Coloring Bipartite Multigraphs in O(E log D)Time,” Combinatorica 21 (2001), pp. 5-12.
[4] K. Fukuda and T. Matsui, “Finding All the Perfect Matchings in Bipartite Graphs,”
Applied Mathematics Letters 7 (1994), pp. 15-18.
[5] L. A. Goldberg, “Efficient Algorithms for Listing Combinatorial Structures,” Cambridge University Press, New York, (1993).
[6] D. S. Johnson, M. Yanakakis and C. H. Papadimitriou, “On Generating All Maximal
Independent Sets,” Information Processing Letters, 27 (1998), pp. 119–123.
[7] S. Kapoor, and H. Ramesh, “An Algorithm for Enumerating All Spanning Trees ofa Directed Graph,” Algorithmica 27 (2000), pp. 120-130.
[8] D. König, “Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlhere,” Math. Ann. 77 (1916), pp. 453-465.
[9] D. L. Kreher and D. R. Stinson, “Combinatorial Algorithms,” CRC Press, Boca
Raton, (1998).
[10] S. Nakano, T. Uno, “Constant Time Generation of Trees with Specified Diameter,”
Lecture Notes in Computer Science 3353, Springer-Verlag, (2004) pp. 33-45.

On the Enumeration of Bipartite Minimum Edge Colorings

15[11] R. C. Read and R. E. Tarjan, “Bounds on Backtrack Algorithms for Listing Cycles,
Paths, and Spanning Trees,” Networks 5, 237-252 (1975).
[12] Y. Yoshida, Matsui and T. Matsui, “Finding All the Edge Colorings in Bipartite
Graphs,” T.IEE. Japan 114-C 4 (1994), pp. 444-449 (in Japanese).
[13] Y. Matsui, and T. Matsui, “Enumeration Algorithm for the Edge Coloring Problem
on Bipartite Graphs,” Lecture Notes in Computer Science 1120, Springer-Verlag,(1996), pp. 18-26.
[14] S. Nakano, “Enumerating Floorplans with n Rooms,” Lecture Notes in Computer
Science 1350, Springer-Verlag, (2001), pp. 107-115.
[15] A. Schrijver, “Bipartite Edge-Colouring in O(∆m) Time,” SIAM Journal on Computing 28 (1999), pp. 841–846.
[16] A. Shioura, A. Tamura, and T. Uno, “An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs, ” SIAM Journal on Computing 26 (1997), pp. 678692.
[17] Takeaki
Uno“Two
General
Methods
toReduceDelayand
Change of Enumeration Algorithms,” NII Technical Report, (2004),
http://research.nii.ac.jp/TechReports/index.html[18] H. S. Wilf, “Combinatorial Algorithms : An Update”, SIAM, (1989).
Yasuko MATSUI
Department of Mathematical Sciences, Faculty of Science, Tokai University, 1117, Kitakaname, Hiratsuka-shi, Kanagawa, Japan yasuko@ss.u-tokai.ac.jp
Takeaki UNO
National Institute or Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, JAPAN.
e-mail: uno@nii.jp