Minimum cycle and homology bases of surface embedded graphs

2016/07/18 by Borradaile, Glencora, Chambers, Erin Wolf, Fox, Kyle +1
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1607.05112

Abstract

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (ℤ₂)-homology classes) of an undirected graph embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^ω+2^2gn²+m)-time algorithm for graphs embedded on an orientable surface of genus g. The best known existing algorithms for surface embedded graphs are those for general graphs: an O(m^ω) time Monte Carlo algorithm and a deterministic O(nm²/log n + n² m) time algorithm. For the minimum homology basis problem, we give a deterministic O((g+b)³ n log n + m)-time algorithm for graphs embedded on an orientable or non-orientable surface of genus g with b boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of g and n. The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of O(log n).

Related

• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
• Minimum Cuts in Surface Graphs
• Holiest Minimum-Cost Paths and Flows in Surface Graphs
• Minimum-cost integer circulations in given homology classes
• Fast Algorithms for Minimum Homology Basis