Files in this item



application/pdfKyle_Fox.pdf (3MB)
(no description provided)PDF


Title:Fast algorithms for surface embedded graphs via homology
Author(s):Fox, Kyle J.
Director of Research:Erickson, Jeff G.
Doctoral Committee Chair(s):Erickson, Jeff G.
Doctoral Committee Member(s):Chekuri, Chandra S.; Hoiem, Derek W.; Eppstein, David
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):computational topology
topological graph theory
minimum cut
maximum flow
non-trivial cycles
Abstract:We describe several results on combinatorial optimization problems for graphs where the input comes with an embedding on an orientable surface of small genus. While the specific techniques used differ between problems, all the algorithms we describe share one common feature in that they rely on the algebraic topology construct of homology. We describe algorithms to compute global minimum cuts and count minimum s,t-cuts. We describe new algorithms to compute short cycles that are topologically non-trivial. Finally, we describe ongoing work in designing a new algorithm for computing maximum s,t-flows in surface embedded graphs. We begin by describing an algorithm to compute global minimum cuts in edge weighted genus g graphs in g^O(g) n log log n time. When the genus is a constant, our algorithm’s running time matches the best time bound known for planar graphs due to Łącki and Sankowski. In our algorithm, we reduce to the problem of finding a minimum weight separating subgraph in the dual graph and provide two subroutines tailored to different kinds of separating subgraphs. We describe algorithms to compute short non-trivial cycles in edge weighted graphs. Some of the algorithms are tailored to take advantage of undirected edge weights, but others are designed to work in graphs where the edges are directed. For undirected graphs embedded on surfaces of genus g, our algorithms compute non-separating, non-contractible, and non-null-homologous cycles in 2^O(g) n log log n time, improving the previous best algorithms of Italiano et al. which run in g^O(g) n log log n time. For directed graphs, we give an algorithm to compute shortest non-null-homologous cycles in O(g^2 n log n) time, matching the running time of Erickson’s algorithm for computing shortest non-separating cycles. We also give an O(g^3 n log n) time algorithm for computing shortest non-contractible cycles in directed graphs. This last result improves upon the previous best algorithm by Erickson which runs in g^O(g) n log n time. We describe an algorithm to count minimum s,t-cuts. Despite the problem being #P-complete in general graphs, our algorithm runs in 2^O(g) n^2 time. After running our algorithm once it becomes possible to sample minimum cuts uniformly at random in O(n log n) time per sample. This result directly generalizes an O(n^2) time algorithm for counting minimum s,t-cuts in planar graphs by Bezáková and Friedlander. Like Bezáková and Friedlander, we reduce the problem of counting minimum s,t-cuts to one of counting forward t,s-cuts in an embedded directed acyclic graph. Finally, we describe ongoing work toward computing maximum s,t-flows. Borradaile and Klein describe an O(n log n) time algorithm to compute maximum s,t-flows in planar graphs. We give a new algorithm that appears to generalize their techniques naturally to surfaces with positive genus, and similar to their algorithm we are able to send flow down augmenting paths in O(g log n + g^2) amortized time per path. We prove that our algorithm performs a quadratic number of augmentations, giving it an overall time bound of O(g n^2 (log n + g)). While we have been unable to find a proof so far, we believe our algorithm may actually run in near-linear time when the surface has constant genus.
Issue Date:2014-01-16
Rights Information:Copyright 2013 Kyle J. Fox
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12

This item appears in the following Collection(s)

Item Statistics