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 ***
DIMACS Home Page