Well begun is half done: the computation of Eulerian paths

Abstract

We characterize the uniform computational strength of finding (one-way or two-way, directed or undirected) Eulerian paths in countable graphs. In the one-way case, for both directed and undirected graphs, this problem is Weihrauch-equivalent to $\mathsf{lim}\times {\mathsf{C}}_{\mathbb{N}}^{\prime }$, where ${\mathsf{C}}_{\mathbb{N}}^{\prime }$ is the jump of closed choice on the natural numbers. This refines the proof-theoretic strength of the existence of a one-way Eulerian path given by the reverse mathematics framework. The ${\mathsf{C}}_{\mathbb{N}}^{\prime }$ component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to $\mathsf{lim}$, which also characterizes the degree of the two-way directed/undirected Eulerian path problem. We also study the complexity of orienting the edges of a graph while preserving the existence of a one-way/two-way Eulerian path. In the one-way case, this problem is not computable, and we prove that ${\mathsf{lim}}_2{<}_{\mathrm{W}}\mathsf{OrientEP}{<}_{\mathrm{W}}{\mathsf{C}}_2^{\prime }\sqcap {\mathsf{Sort}}_2$ and $\mathsf{OrientEP}/{\le }_{\mathrm{W}}{\mathsf{C}}_{\mathbb{N}}$. On the other hand, valid orientations are uniformly computable for two-way paths and for one-way paths with a prescribed valid starting vertex.