Hierholzer's Algorithm

Hierholzer's algorithm is a linear-time O(E) graph algorithm in computation and algorithms that constructs an Eulerian circuit (or Eulerian trail) in a connected undirected or directed multigraph—a closed walk (or open walk) that traverses every edge of the graph once and only once. Formulated by German mathematician Carl Hierholzer shortly before his death in 1871 and published posthumously by his colleagues in Mathematische Annalen in 1873, the paper provided the first rigorous converse to Leonhard Euler's 1736 solution of the Seven Bridges of Königsberg problem, proving that degree parity and connectivity are both necessary and sufficient for the existence of an Eulerian circuit.

Within computational complexity theory and modern algorithmic bioinformatics, Hierholzer's algorithm is the standard linear-time procedure for Eulerian tour construction. Unlike Fleury's algorithm (1883), which must test at every step whether a candidate edge is a graph bridge in O(E²) or O(E log² V) time, Hierholzer's algorithm greedily follows unused edges to close simple cycles and splices detour sub-cycles into the main tour via a stack in O(V + E) optimal time. This capability underpins shotgun genome assembly over De Bruijn graphs as well as route inspection and VLSI layout synthesis.

Eulerian Circuits and Trails in Undirected and Directed Multigraphs

Let G = (V, E) be a finite multigraph (allowing parallel edges and self-loops) with vertex count V = |V| and edge count E = |E|.

• An Eulerian trail (or Eulerian path) is a walk in G that traverses every edge e ∈ E once.
• An Eulerian circuit (or Eulerian tour / Eulerian cycle) is a closed Eulerian trail that starts and ends at the same vertex.
• A graph is Eulerian if it possesses an Eulerian circuit, and semi-Eulerian if it possesses an Eulerian trail that is not closed.

Assuming all vertices of nonzero degree belong to a single connected component (in the undirected case) or a single strongly connected component (in the directed case, with weak connectivity for semi-Eulerian trails), the Euler–Hierholzer Theorem characterizes existence completely via local vertex degrees:

1. Undirected Multigraphs:
   • G has an Eulerian circuit if and only if every vertex v ∈ V has even degree (deg(v) ≡ 0 mod 2).
   • G has an open Eulerian trail between s and t (s ≠ t) if and only if s and t have odd degree and every other vertex v ∈ V \ {s, t} has even degree.
2. Directed Multigraphs:
   • G has a directed Eulerian circuit if and only if every vertex v ∈ V is balanced, meaning its in-degree equals its out-degree: deg⁻(v) = deg⁺(v).
   • G has a directed Eulerian trail from s to t (s ≠ t) if and only if deg⁺(s) − deg⁻(s) = 1, deg⁻(t) − deg⁺(t) = 1, and deg⁻(v) = deg⁺(v) for all v ∈ V \ {s, t}.

Cycle Decomposition and the Splicing Invariant

Hierholzer's constructive proof rests on the Degree-Parity Preservation Lemma: in any graph where every vertex has even degree (or balanced in-degree and out-degree), any maximal walk that starts at a vertex v₀ and repeatedly traverses previously unused edges without repeating any edge cannot get stuck at any vertex other than v₀.

Proof: Whenever the walk enters an intermediate vertex u ≠ v₀ along an unused incoming edge, it consumes 1 unit of u's remaining degree (or 1 unit of in-degree). Because u began with an even degree (or equal in-degree and out-degree) and each previous pass through u consumed pairs of one incoming and one outgoing edge, at least one unused outgoing edge incident to u must remain available. Thus the walk can only terminate when it returns to the starting vertex v₀, forming a closed cycle C₁.

Removing the edges of C₁ from G leaves a residual subgraph G′ = (V, E \ E(C₁)) in which every vertex still has even degree (or balanced in/out-degree) because C₁ removed an equal number of incoming and outgoing edges at every vertex it visited. If E \ E(C₁) ≠ ∅, connectivity of G guarantees that at least one vertex w visited by C₁ still has unused incident edges in G′. Launching a second greedy walk from w in G′ closes a second edge-disjoint cycle C₂, which can be spliced directly into C₁ at w to form a longer closed walk. Repeating until all E edges are exhausted yields a complete Eulerian circuit.

Stack-Based Post-Order Cycle Splicing

Rather than maintaining linked lists to splice sub-cycles explicitly, modern implementations of Hierholzer's algorithm use a single traversal stack S and an output list L alongside current-arc pointers (identical to the pointer-advance technique in Dinic's algorithm):

1. Initialization: Push the starting vertex v₀ onto the active stack S = [v₀], and initialize an empty circuit list L = []. (If computing an open Eulerian trail from odd/excess vertex s to t, either start at s or temporarily add a virtual edge (t, s) to close the circuit and split the output tour at (t, s) upon completion.)
2. Stack Loop: While S is nonempty, inspect the vertex u = top(S):
   • Advance Along Unused Edge: If u has an unused outgoing incident edge e = (u, v) (found in O(1) amortized time by advancing u's adjacency pointer past any already deleted edges), mark e as used/deleted and push v onto S.
   • Retreat and Output (Splicing): If u has no remaining unused incident edges, pop u from S and append u to the output list L.
3. Finalization: Reverse L (for directed graphs) to obtain the ordered sequence of E + 1 vertices forming the Eulerian circuit.

Why Stack Popping Automatically Splices Cycles in O(E) Time

When the initial greedy walk closes a cycle C₁ back to v₀ and v₀ has no remaining unused edges, the algorithm pops vertices from the end of C₁ onto L until it backtracks to the last vertex w on C₁ that still possesses unused incident edges. Before popping w or any prefix of C₁ preceding w, the stack grows from w to trace out the entire detour sub-cycle C₂ (and any nested sub-cycles inside C₂) and pops all of C₂ into L before resuming the pop of the prefix of C₁. Because each edge e ∈ E is pushed onto S once and popped from S once, both time and space complexity are strictly O(V + E).

Comparison of Eulerian and Route-Inspection Algorithms

1. De Novo Genome Assembly via De Bruijn Graphs (Pevzner, Tang, and Waterman, 2001): Instead of formulating shotgun DNA sequence assembly as an NP-hard Hamiltonian path problem on an overlap graph, Eulerian assemblers (EULER, SPAdes, Velvet) break sequencing reads into (k − 1)-mer vertices and k-mer directed edges in a De Bruijn graph, reconstructing genomic contigs as Eulerian trails via Hierholzer's algorithm.
2. De Bruijn Sequence Generation and Combinatorial Gray Codes: Constructing a cyclic sequence of length σ^k over an alphabet of size σ containing every possible length-k substring once reduces to running Hierholzer's algorithm on the σ-ary De Bruijn graph on σ^k−1 vertices.
3. CMOS VLSI Standard-Cell Layout (Euler Path Gate Chaining): In complementary metal-oxide-semiconductor (CMOS) physical design, pull-up PMOS and pull-down NMOS transistor dual graphs are chained into contiguous diffusion strips without isolation breaks by finding common Eulerian trails across the series-parallel dual multigraphs.

Why is Hierholzer's algorithm preferred over Fleury's algorithm?

Fleury's algorithm requires checking at every vertex whether a candidate edge is a bridge of the remaining graph (an edge whose removal disconnects the remaining non-isolated vertices). Testing bridge status via DFS at each of the E steps takes O(E²) time (or O(E log² V) using dynamic graph connectivity structures), whereas Hierholzer's algorithm requires zero connectivity queries during traversal and runs in O(V + E) time.

How does Hierholzer's algorithm handle graphs with parallel edges in an undirected representation?

In an undirected multigraph, each edge e = {u, v} is assigned a unique edge index id ∈ {0, …, E − 1} stored alongside both endpoints' adjacency lists, and a boolean array *used*[id] ensures that traversing e from u to v immediately marks its reverse entry at v as used in O(1) time.

1. Hierholzer, C., & Wiener, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen, 6(1), 30–32. https://doi.org/10.1007/BF01442866
2. Euler, L. (1741). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae, 8, 128–140. https://doi.org/10.5479/sil.318525.39088000877480
3. Edmonds, J., & Johnson, E. L. (1973). "Matching, Euler tours and the Chinese postman." Mathematical Programming, 5(1), 88–124. https://doi.org/10.1007/BF01580113
4. Pevzner, P. A., Tang, H., & Waterman, M. S. (2001). "An Eulerian path approach to DNA fragment assembly." Proceedings of the National Academy of Sciences, 98(17), 9748–9753. https://doi.org/10.1073/pnas.171285098