Computation of cycle bases in surface embedded graphs

Joint work with Thomas Stanley

Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), 13:1–10:13, 2022

pdf

Abstract

We present an \(O(n^3 g^2\log g + m)\) + \(\tilde{O}(n^{\omega + 1})\) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus \(g\). This result improves upon the previous fastest known running time of \(O(m^3n + m^2n^2 \log n)\) applicable to general directed graphs.

While an \(O(n^{\omega} + 2^{2g}n^2 + m)\) time deterministic algorithm was known for undirected graphs, the use of the underlying field \(\mathbb{Q}\) in the directed case (as opposed to \(\mathbb{Z}_2\) for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an \(O(n^{\omega} + n^2 g^2 \log g + m)\) time deterministic algorithm for undirected graphs as well.