Well begun is half done: the computation of Eulerian paths
math.LO, math.CO
Submitted: 2026-10-31
Updated: 2026-11-04
License: http://creativecommons.org/licenses/by/4.0/
The gist: We characterize the uniform computational strength of finding (one-way or two-way, directed or undirected) Eulerian paths in countable graphs.
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 times N', where N' 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 N' component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to, 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 2< W < W 2' 2 and at most W 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.
Related papers
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- The Additive Arithmetic of Linear Orders
- Indiscernible Extraction in Theories with Bounded k-splitting
- Measuring the Complexity of Countable Presburger Models
- A non-trivially non-trivial automorphism at an inaccessible cardinal