Short-Length Menger Theorems
Monika Rauch Henzinger, Jon M. Kleinberg, Satish B. Rao · 1997
We give short and simple proofs of the following two theorems by Galil and Yu [3]. Let s and t be two vertices in an n-node graph G. (1) There exist k edge-disjoint s-t paths of total length O(n √ k). (2) If we additionally assume that the minimum degree of G is at least k,then there exist k edge-disjoint s-t paths, each of length O(n/k). Let G = (V, E) be an undirected n-node graph, with no parallel edges, and let s and t be two vertices of G such that there exist k edge-disjoint s-t paths. Our goal is to give short proofs of the following two theorems of Galil and Yu [3]. Theorem 1 There exist k edge-disjoint s-t paths of total length O(n √ k). Theorem 2 If we additionally assume that the minimum degree of G is at least k, then there exist k edge-disjoint s-t paths, each of length O(n/k). We view G as a directed graph by replacing each undirected edge by two oppositely oriented directed edges. Our proof of the first theorem is based on a maximum flow algorithm of Even and Tarjan [2]; for our purposes, we need only consider