Minimum cuts and shortest non-separating cycles via homology covers

Let G be a directed graph with weighted edges, embedded on a surface of genus g. We describe an algorithm to compute a shortest directed cycle in G in any given ℤ₂-homology class in 2^O(g)n log n time; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute a shortest non-separating directed cycle in G in 2^O(g)n log n time, improving the recent algorithm of Cabello et ai [SOCG 2010] for all g = o(log n). The second is a combinatorial algorithm to compute minimum (s, t)-cuts in undirected surface graphs in 2^O(g)n log n time, improving on previous combinatorial algorithms, and in particular the recent of Chambers et ai [SOCG 2009], for all g - o(log n). Unlike earlier algorithms for surface graphs that construct and search finite portions of the universal cover, our algorithms use another canonical covering space, called the ℤ₂-homology cover.