Potentials in Undirected Graphs and Planar Multiflows
András Sebö · SIAM Journal on Computing · 1997
The duality relation between shortest paths and potentials in directed graphs and the significance of both of these in the theory of network flows is well known. In thispaper, we work out the analogous undirected notions, which neither are contained in nor contain their directed counterpart. They are more related to matching theory than to network flows: the corresponding min-path-max-potential theorem can be considered a weighted generalization of the Gallai--Edmonds structure theorem for matchings. In our earlier work [J. Combin. Theory Ser. B, 49 (1990), pp. 10--39], the corresponding theorems are proved in the special case of $\pm 1$ bipartite weightings, and this special case already contains the main points of the general proof. The goal of the present paper is to extrapolate from this $\pm 1$-weighted bipartite special case the arbitrarily weighted general min-path-max-potential theorem and to show some algorithmic consequences related to planar multiflows, the Chinese postman problem, the weighted and unweighted matching structure, etc. In order to make this paper self-contained, we also include a compact, revised variant of earlier proofs, adapted to the present context. In addition to good characterization theorems and polynomial algorithms, efficient (logarithmic polynomial) parallel algorithms follow for some of these problems.