Minimum cycle and homology bases of surface-embedded graphs

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 $(mathbb{ Z}_ 2 )$-homology classes) of an undirected graph cellularly 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^{ 2 g}  n^ 2 + m )$-time algorithm for graphs cellularly embedded on an orientable surface of genus $ g$ . Prior to this work, the best known algorithms for surface-embedded graphs were those for general graphs: an $ O ( m^ ω )$-time Monte Carlo algorithm  and a deterministic $ O ( nm^ 2 / log+ n^ 2 m )$-time algorithm .For the minimum homology basis problem, we give a deterministic $ O (( g + b )^ 3 n log+ m )$-time algorithm for graphs cellularly embedded on an orientable or non-orientable surface of genus $ g$  with $ b$  boundary components, improving on existing algorithms for many values of $ g$  and $ n$ . The algorithm assumes that shortest paths are unique; this assumption can be avoided by either using random perturbations of the edge weights guaranteeing a high probability of success or by deterministic means at a cost of an $ O (log)$ factor increase in running time.