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 lg m) bits of working memory.This substantially improves the working space compared to standard implementations of Hierholzer's algorithm, which use O(m lg 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.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.