Fast algorithms for surface embedded graphs via homology

Fox, Kyle J.

Permalink

https://hdl.handle.net/2142/46579 Copy

Description

Title

Fast algorithms for surface embedded graphs via homology

Author(s)

Fox, Kyle J.

Issue Date

2014-01-16T17:54:48Z

Director of Research (if dissertation) or Advisor (if thesis)

Erickson, Jeff G.

Doctoral Committee Chair(s)

Erickson, Jeff G.

Committee Member(s)

• Chekuri, Chandra S.
• Hoiem, Derek W.
• Eppstein, David

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• computational topology
• topological graph theory
• Homology
• 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.

Graduation Semester

2013-12

Permalink

http://hdl.handle.net/2142/46579

Copyright and License Information

Copyright 2013 Kyle J. Fox

Owning Collections