SMALL INTEGRAL FLOWS NEED ONLY SPARSE NETWORKS

Consider a network on n + 1 vertices and two s - t-flows f and f of e qual value. f is called a flow spanner of f if f*(e) less-than-or-equ al-to f(e) for every edge e. In this note, we prove that every integra l flow f of value n2-epsilon (0 less-than-or-equal-to epsilon less-tha n-or-equal-to 2) has a flow spanner f that uses at most 0 (n2-epsilon /2) many edges. A sequence of examples shows that this result is asymp totically optimal. (C) 1994 John Wiley & Sons, Inc.