My first open problem

In the winter of 2026, I started an undergraduate research assistantship (URA) with Prof. Elena Grigorescu (opens in a new tab).

I began thinking about Hierholzer’s algorithm, a classical algorithm for finding Euler tours that I remembered from my Olympiad days. The question was how to keep its linear running time while using much less memory. A solution existed for directed graphs, but the undirected case was still open. Thinking it couldn’t be that hard, I started working on it.

After eight months of pain and tears, I had a solution. That work led to Space-Efficient Hierholzer for Undirected Graphs (opens in a new tab).

The algorithm outputs an Euler tour of an undirected multigraph, if one exists, in O(m) time using O(n) words of working memory, where n is the number of vertices and m the number of edges. You can see how it works here (opens in a new tab).

It all felt impossible until it didn’t. The hardest part was to keep going.