Christian Fremuth-Paeger and Dieter Jungnickel

Balanced Network Flows

A New Framework for Matching Theory

During this project, we have investigated a network flow model for capacitated matching problems. This approach to matching theory is very intuitive since many techniques and results can be adopted from standard flow theory to balanced network flows. We have investigated the non-weighted part very thoroughly. We have alo researched weighted problems, but leave some open questions.

Balanced flow networks are defined on skew-symmetric digraphs. The inherent symmetry of a skew-symmetric digraph is not really a graph isomorphism, but flips the arc directions. The mapping is self-inverse, and nodes, arcs and paths which map to each other are called complementary. In balanced flow networks, complementary arcs have equal integral capacities and equal cost labels. An example of a skew-symmetric digraph is given below.

o


An integral flow with equal flow values on complementary arcs is called balanced. A fractional flow with equal flow values on complementary arcs is called fractional balanced. A maximum half-integral balanced flow can be derived from any maximum integral flow by a simple operation. On the other hand, maximum balanced flows are maximum flows only in special circumstances. Hence integrality is a crucial part of balanced network flow problems.


Reduction Principles

Non-weigthed matching problems form part of the problem of finding a maximum balanced flow. Weighted matching problems are special cases of the problem of finding a balanced circulation of minimum costs. The reduction mechanism is really simple, and can be explained by an example:

Consider the cardinality matching problem which is one of the most important problems in combinatorial optimization. One asks for a maximum set of graph edges which have no end nodes in common. This problem can be reduced to 0-1 balanced flow networks. For instance, the graph (b), as follows, is transformed into the balanced flow network from above.

o

The obvious idea is to split every node of the original graph into a pair of complementary nodes. If we are concerned with bipartite matching problems, we also could use a well-known problem reduction to the max flow problem without splitting the graph nodes. For instance, the graph (a) would be transformed into this flow network:

o


There also is a reverse reduction mechanism which transforms balanced flow networks into instances of the so-called c-capacitated b-matching problem. This reduction mechanism is also linear, but less intuitive, and not as interesting for algorithmic purposes. But it eventually shows that the min-cost balanced circulation problem and c-capacitated b-matching problem are equivalent in a strong sense.

Last not least, lower bounds on a balanced flow network can be handled by transformation to the maximum balanced st-flow problem. A corresponding problem reduction for ordinary flows was invented by Ford and Fulkerson long ago.


Augmentation

Not surprisingly, a maximum balanced st-flow can be found by pushing flow along paths with residual capacity: One tries to augment by an st-path, and by its complementary st-path likewise. If simultanious augmentation is indeed possible, these paths are called valid. If no such paths exist, the given balanced st-flow is proved to be maximum balanced.

If one can determine valid augmenting paths of minimum length efficiently, the resulting algorithm is polynomial, too. Similar results are known for the max flow problem and the cardinality matching problem. There are even more analogies between matching and network flow problems since balanced circulations of minimum costs can be described by valid cycles as well:

All of these optimality results can be established by application of a flow decomposition theorem which splits the difference between two feasible balanced circulations into elementary flows supported by valid paths.


Blossoms

In the literature on capacitated matching problems, you will find two different, but strongly related notions of odd sets: Blossoms which are determined by matching algorithms, and nuclei which occur in duality theorems. Both notions coincide for the cardinality matching problem.

Blossom and nuclei are connected components of certain subgraphs in a balanced network. Blossoms are induced by the so-called bicursal arcs, nuclei by a certain node set, called the core. Blossoms are nested into nuclei, and the node set of a nucleus splits into the node set of a series of blossoms. Blossoms and nuclei coincide if the network has unit node capacities, that is, a node is reached or left by at most one arc which has unit capacity.

Below, you can see a graph, and one of its subgraphs which consists of the boldfaced arcs. If we would search for a 2-factor, the residual balanced network would have the blossoms B(s)={s,t,7,7',8,8',11,11',12,12',13,13'} and B(3')={1,1',3,3',4,4'}, and one nucleus which is the union of this blossoms.

o



Layered Auxiliary Networks

The balanced network search (BNS) checks which nodes of the network are reachable on valid paths from a certain node s. There should be an opportunity to extract valid paths later when neccessary.

BNS algorithms (or at least their analysis) depend on layered auxiliary networks which correspond to shrinking the blossoms in the original graph matching problem. Layered auxiliary networks are not present explicitly, but determined by a disjoint set union structure, and certain arcs of the network which are called props.

Blossoms and nuclei contain a unique node which is traversed by every valid path which connects the source s to a node in the blossom. This node is called the base, and present in the disjoint set union structure. The nodes of a layered auxiliary network are blossom bases. The layer, where a blossom base is placed in the network, is determined by a distance label.

In simple BNS algorithms, the layered auxiliary networks are arborescences rooted at s. In BNS algorithms which determine valid paths of minimum length, as well as in the general situation, the layered auxiliary networks are acyclic networks rooted at s, but no trees.

As an example, consider the following residual network which belongs to a 2-factor problem. The layered axiliary network is obtained by shrinking the two depicted blossoms (that is, identifying all internal nodes). This network is not an arborescence, indeed.

o



Balanced Network Search

We have shown how reachability evolves if a complementary pair of arcs a and a' is investigated by some matching algorithm. The results use layered auxiliary networks, and make only slight consumptions about the search order of the algorithm. By our theory, the known matching algorithms of Edmonds, Micali/Vazirani, Kocay/Stone, Kameda/Munro, and probably other algorithms can be analysed in their effects.

There are two situations which can occur by the investigation of a and a'. The first one, we have called 'bud generation'. Here nodes v can become reachable only if the complementary node is not reachable yet. One assigns a or a' as a prop to v. This arc is added to the layered auxiliary network then.

The other situation is called 'blossom shrinking'. Here nodes v can become reachable only if the complementary node has been reached before. One assigns a petal to v. The layered auxiliary network is updated by merging all blossoms into a single set which have been traversed during the double depth first search (DDFS).

This non-trivial operation determines the nodes which become reachable by adding a and a'. Loosely speaking, the DDFS tries to find two independent paths in the layered auxiliary network, both starting at s, one ending at the start node of a, the other ending at the start node of a'. The DDFS has been designed originally for the Micali/Vazirani algorithm, but can be adopted to the BNS in general.


Algorithms

The balanced augmentation algorithm has polynomial time complexity only if either the augmenting paths have minimum length, or if we are concerned with special matching problems. It the former case, we would obtain an O(n m^2) algorithm. In the latter, we would obtain an O(n m) algorithm for k-factor problems (where k is fixed, and graphs are simple). Besides the straight balanced augmentation algorithm, there are the following ideas to compute maximum balanced flows:

If we determine valid augmenting paths of minimum length only, the length of the augmenting paths may not decrease. A layered auxiliary network has to be computed only if the path length strictly increases. This modified algorithm is an synthesis of the max flow algorithm of Dinic and the Micali/Vazirani algorithm to an O(n^2 m) method which applies to all kinds of non-weighted matching and balanced network flow problems.

One can improve the balanced augmentation algorithm by scaling techniques also. There are two ways to do this: One can either run the balanced augmentation algorithm on a series of networks. The last one is the original network, and every network is obtained from its successor by dividing the capacities by two. One can also determine augmenting paths which have a minimum capacity. This lower bound is divided by two if no further augmenting paths can be found. Both algorithms would run in O(m^2 log(U)) time.

The latter idea has a major advantage: One can determine arbitrary augmenting paths unless the last scaling phase is reached. This is, of course, much more efficient. The algorithm is somewhat similar to Anstee's approach:

Here, an arbitrary maximum flow is determined first. This flow is then symmetrized so that flow values may turn half-integral. From this flow, one can obtain a balanced flow which is not maximum yet, but requires only a few balanced augmentation steps. If we consider matching problems only, this last step is a rather simple procedure.

All steps together need O(n m) time. The critical part is the determination of the initial maximum flow. Hence the Anstee algorithm is state-of-the-art. As a major advantage, we can combine numerous max flow algorithms with various BNS procedures.


Weighted problems

There is a valuable paper by Goldberg and Karzanov which concerns an algorithm for finding shortest valid augmenting paths in the weighted setting. As known from the 1-matching problem, the primal-dual (PD) and the shortest augmenting path (SAP) are almost equivalent.

We have researched an explicit PD-algorithm plus the startup procedure which makes the method strongly polynomial (The general idea is similar to the non-weighted setting). We did not work out the details of high-performance implementations of the PD-scheme which may be closely related to the 1-matching case but which turn some additional technical difficulties. We have also worked out the application to the shortest valid path problem.

To our knowledge, the primal approach has not been applied to balanced circulations yet. We suggest that primal algorithms and postoptimzation procedures would deserve further research. Interested people may contact us for a research cooperation.

Publications and Preprints

Below, you can find references to our previous publications as well as postscript versions of our recent reports. Preprints/reprints may be requested by the authors.

Download Poster Presentation

Matching Source Code

We have prepared a C++ solver for all kind of matching problems for download, including

Our solver supports the balanced network flow algorithms based on augmentation (weighted and non-weighted), phase ordered augmentation (non-weighted), and canceling of fractional cycles (weighted and non-weighted). The latter algorithm can be combined with several max-flow and min-cost flow algorithms.

The matching solver program is an extraction of the C++ class library GOBLIN which is dedicated to graph optimization problems in general.

GOBLIN Download Page

Source code for matching algorithms is also available at
Back to my Homepage E-Mail me
o o o o
Christian Fremuth-Paeger, July 2000