DIMACS TR: 93-44

Half-integral flows in a planar graph with four holes

Author: Alexander V. Karzanov


This report contains an improved and shorter proof of the four-hole flow theorem obtained in an earlier paper of the author. Suppose we are given an undirected planar graph G and a collection U of pairs of its vertices to be connected by flows of unit value. We assume that the graph G+U is eulerian, and that there is a subset H of faces of G such that each pair in U belongs to the boundary of some face in H.

It is known, due to Okamura and Seymour, Okamura, Karzanov, that if |H| is 1, 2 or 3 and the multicommodity flow problem for G and U has a solution then it has an integral solution as well. Such a property does not remain true for |H|=4. We prove that if |H|=4 and if the problem for G and U has a solution then it has a half-integral solution.

*** This report not available on line ***

Paper only.

DIMACS Home Page