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 directed (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.

Undirected graphs

Unlike hinted at in the SOSA 2026 version, the algorithm presented in this paper does not seem to easily extend to a space-efficient algorithm for undirected graphs. We instead found that a rather different approach works. Albeit still based on Hierholzer’s algorithm, the techniques are different. That latter approach provably does not work on directed graphs; hence the results are orthogonal.

Try it out!   (Interactive demo)