Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space

We describe a simple variant of Hierholzer’s algorithm that finds an Eulerian cycle in a (multi)graph with $n$ vertices and $m$ edges using $O(n \log m)$ bits of working memory. This substantially improves the working space compared to standard implementations of Hierholzer’s algorithm, which use $O(m \log n)$ bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an $O(m)$-size stack of vertices or storing information for each edge.

This is the first linear-time algorithm to achieve this space bound, and the method is very easy to implement. The correctness argument, by contrast, is surprisingly subtle; we give a detailed formal proof. The space savings are particularly relevant for dense graphs or multigraphs with large edge multiplicities.