Holiest minimum-cost paths and flows in surface graphs

With Kyle Fox and Luvsandondov Lkhamsuren*.

To appear in Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, 2018.

Let G be an edge-weighted directed graph with n vertices embedded on a surface of genus g. We describe a simple deterministic lexicographic perturbation scheme that guarantees uniqueness of minimum-cost flows and shortest paths in G. The perturbations take O(gn) time to compute. We use our perturbation scheme in a black-box manner to derive a deterministic O(n log log n) time algorithm for minimum cut in directed edge-weighted planar graphs and a deterministic O(g²n log n)-time preprocessing scheme for the multiple-source shortest path problem of computing a shortest path oracle for all vertices lying on a common face of a surface-embedded graph. The latter result yields faster deterministic near-linear time algorithms for a variety of problems in constant-genus surface-embedded graphs.

Finally, we open the black box to generalize a recent linear-time algorithm for multiple-source shortest paths in unweighted undirected planar graphs to work in arbitrary surfaces. Our algorithm runs in O(g²n log g) time in this setting, and can be used to give improved linear-time algorithms for several problems in unweighted, undirected, surface-embedded graphs of constant genus, including the computation of minimum cuts, shortest topologically non-trivial cycles, and minimum homology bases.

Publications - Jeff Erickson (jeffe@illinois.edu) 13 Feb 2018