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

Abstract:

LetGbe 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 inG. The perturbations take O(gn) time to compute. We use our perturbation scheme in a black-box manner to derive a deterministic O(nlog logn) time algorithm for minimum cut in directed edge-weighted planar graphs and a deterministic O(g²nlogn)-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²nlogg) 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