PreprintCC BY 4.0arXiv
Well begun is half done: the computation of Eulerian paths
Abstract
We characterize the uniform computational strength of finding one-way Eulerian paths in countable graphs. For both directed and undirected graphs, this problem is Weihrauch-equivalent to lim×Cℕ', where Cℕ' is the jump of closed choice on the natural numbers. This refines the proof-theoretical strength of the existence of an Eulerian path given by the reverse mathematics framework. The Cℕ' component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to lim. We also study the problem OrientEP of orienting an undirected graph while preserving the existence of a one-way Eulerian path. We prove lim2<WOrientEP<WC2'sqcapSort2 and OrientEPnot≤WCℕ.
Related
- Real-rooted Eulerian polynomials from permutations, words, and paths
- Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
- Impact Mechanism of a Point Interaction in the Cubic Half-Wave Equation: Well-Posedness, Constrained Energy Levels and Near-Critical Rigidity
- Local well-posedness of the higher-order nonlinear Schrödinger equation on the half-line: the case of two boundary conditions
- Well-posedness of the Burgers' equation on the half-line through the Cole-Hopf transformation
BibTeX
@misc{valenti2026well,
title = {{Well begun is half done: the computation of Eulerian paths}},
author = {Manlio Valenti},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00818},
eprint = {2611.00818},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00818},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Well begun is half done: the computation of Eulerian paths
AU - Manlio Valenti
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00818
UR - https://arxiv.org/abs/2611.00818
AB - We characterize the uniform computational strength of finding one-way Eulerian paths in countable graphs. For both directed and undirected graphs, this problem is Weihrauch-equivalent to lim×C_ℕ', where C_ℕ' is the jump of closed choice on the natural numbers. This refines the proof-theoretical strength of the existence of an Eulerian path given by the reverse mathematics framework. The C_ℕ' component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to lim. We also study the problem OrientEP of orienting an undirected graph while preserving the existence of a one-way Eulerian path. We prove lim_2<_WOrientEP<_WC_2'sqcapSort_2 and OrientEPnot≤_WC_ℕ.
ER -