Space-Efficient Hierholzer: Eulerian Cycles in \(\mbox{O}(m)\) Time and \(\mbox{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 \(\mbox{O}(n \lg m)\) bits of working memory. This substantially improves the working space compared to standard implementations of Hierholzer’s algorithm, which use \(\mbox{O}(m \lg n)\) bits of space. Our algorithm runs in linear time, like the classical versions, but avoids an \(\mbox{O}(m)\)-size stack of vertices or storing information for each edge. To our knowledge, 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.