betaFeedback

WorksMathematics

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 lim×CN′\mathsf{lim}\times\mathsf{C}_{\mathbb{N}}', where CN′\mathsf{C}_{\mathbb{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 CN′\mathsf{C}_{\mathbb{N}}' component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to lim\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 lim2<WOrientEP<WC2′⊓Sort2\mathsf{lim}_2<_{\mathrm{W}}\mathsf{OrientEP}<_{\mathrm{W}}\mathsf{C}_{2}'\sqcap\mathsf{Sort}_2 and OrientEP̸≤WCN\mathsf{OrientEP}\not\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.

Introduction

An Eulerian path in a graph is a trail that traverses every edge exactly once. For infinite graphs, one distinguishes between one-way paths, indexed by N\mathbb{N}, and two-way paths, indexed by Z\mathbb{Z}. The classical Erdős-Grünwald-Weiszfeld theorem (see [15 Thm. 3.2.1]) provides a characterization of when a countable graph admits a one-way Eulerian path. Analogous characterizations can be obtained for one-way Eulerian paths on directed graphs [13 Thm. 1], and two-way Eulerian paths for undirected graphs [15 Thm. 3.2.2] and directed graphs [13 Thm. 2].

2020 Mathematics Subject Classification. Primary 03D30; Secondary 05C45, 05C63.

Key words and phrases. Weihrauch reducibility, Eulerian paths, infinite graphs, directed graphs.

The author thanks Jeffry Hirst and Alberto Marcone for useful conversations on the topics of the paper. ChatGPT-6 was used to explore the literature, as well as discuss and critically review some of the proof strategies, and polish the presentation. All suggestions were carefully assessed, and the author takes full responsibility for the correctness of the results.

Eulerian paths have been studied in computable graph theory and reverse mathematics. In [3 Thm. 1], the author observed that there are computable graphs with an Eulerian path, but no computable such path. In contrast, every highly recursive graph (i.e. a locally finite computable graph admitting a computable degree function d:V→Nd: V \to\mathbb{N} mapping every vertex to the number of its neighbors) with an Eulerian path has a computable such path. This result was recently generalized to moderately computable graphs (i.e. computable graphs with a computable degree function d:V→N∪{∞}d: V \to\mathbb{N} \cup\{\infty\}) in [7]. In [8], the authors study the computability of separating infinite graphs into infinite components and how the number of ends affects the complexity of finding infinite simple paths and deciding whether Eulerian paths exist.

From the point of view of reverse mathematics, it has been shown that, even for pre-Eulerian (i.e. satisfying the hypotheses of the Erdős-Grünwald-Weiszfeld theorem) locally finite graphs, the existence of an Eulerian path is equivalent to ACA0\mathrm{ACA}_0 over RCA0\mathrm{RCA}_0 [10 Thm. 12]. However, a closer look at the proof reveals that, while there is a computable graph GG such that every Eulerian path through GG computes ∅′\varnothing', the proof of the existence of an Eulerian path through every pre-Eulerian graph uses ∅′′\varnothing'', therefore leaving a gap.

In this paper, we use the framework of Weihrauch reducibility to analyze the uniform computational strength of the problem of finding (one-way or two-way) Eulerian paths through countable (directed or undirected) graphs.

Definition 1.1. Let EP be the problem that takes as input a countable undirected graph that has a one-way Eulerian path, and outputs a sequence (xn)n∈N(x_n)_{n \in\mathbb{N}} of vertices forming a one-way Eulerian path, and let DEP be the analogous problem on directed graphs. We also write EP2\mathrm{EP}_2 (resp. DEP2\mathrm{DEP}_2) for the problem that takes as input a countable undirected (resp. directed) graph that has a two-way Eulerian path, and outputs a two-way undirected (resp. directed) Eulerian path (xn)n∈Z(x_n)_{n \in\mathbb{Z}}.

We assume that a graph is represented via the characteristic function of its set of vertices and edges.

In Theorem 3.4, we show that

EP≡WDEP≡Wlim⁡×CN′\mathrm{EP} \equiv_{\mathrm{W}} \mathrm{DEP} \equiv_{\mathrm{W}} \lim\times\mathrm{C}'_{\mathbb{N}}

where lim⁡\lim is the limit operator on Baire space and CN′\mathrm{C}'_{\mathbb{N}} is the jump of closed choice on N\mathbb{N} (see § 2.1). This refines the proof-theoretic characterization obtained via the reverse mathematics analysis: while every computable graph G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}) has a ∅′\varnothing'-computable solution, no uniform ∅′\varnothing'-computable procedure produces one. We observe that the gap between EP (or DEP) and lim⁡\lim rests entirely on the complexity of finding the first vertex of the Eulerian path. Once such a vertex is found, the rest of the path can be obtained uniformly in the jump of the input (Theorem 3.2). This also gives an intuitive explanation of why, in contrast to what happens for one-way paths, finding two-way (directed or undirected) Eulerian paths is simpler (Theorem 5.2 and Theorem 5.4):

EP2≡WDEP2≡Wlim⁡.\mathrm{EP}_2 \equiv_{\mathrm{W}} \mathrm{DEP}_2 \equiv_{\mathrm{W}} \lim.

The similarity of the directed and undirected constructions suggests a second question: can we computably orient an undirected graph while preserving the existence of a (one-way or two-way) Eulerian path? In § 4, we study the Weihrauch degree of the problem OrientEP of computing an orientation of the edges of a graph preserving one-way Eulerian paths. We obtain

lim⁡2<WOrientEP⁡<WC2′∩Sort⁡2,OrientEP⁡̸≤WCN.\lim_2 <_{\mathrm{W}} \operatorname{OrientEP} <_{\mathrm{W}} \mathrm{C}'_2 \cap\operatorname{Sort}_2,\qquad\operatorname{OrientEP} \not\leq_{\mathrm{W}} \mathrm{C}_{\mathbb{N}}.

The C2′\mathrm{C}'_2 upper bound is obtained by showing that, for every undirected graph G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}), we can uniformly compute a directed graph DD by orienting the edges of GG such that either DD or its global reversal DopD^{\mathrm{op}} is a valid solution for OrientEP⁡(G)\operatorname{OrientEP}(G) (Lemma 4.4). This implies, e.g. that C3̸≤WOrientEP⁡\mathrm{C}_3 \not\leq_{\mathrm{W}} \operatorname{OrientEP}. The obtained results separate OrientEP from other standard benchmarks in the Weihrauch lattice.

Once again, the complexity of OrientEP can be explained in terms of the complexity of finding the starting vertex of the path. In contrast, the problem OrientEP2_2 of orienting the edges of an undirected graph so that the resulting directed graph admits a two-way Eulerian path is uniformly computable (Theorem 5.6).

Background and notation

We briefly recall the main notions and fix the notation that will be used throughout the paper.

An undirected graph GG is a pair (V,E)(V,E) where VV is the set of vertices and EE is a set of unordered pairs of vertices, called edges. A directed graph is a graph where the edges are ordered pairs. To stress the difference between unordered and ordered edges between two vertices uu and vv, we use {u,v}\{u,v\} to denote the former and (u,v)(u,v) to denote the latter. In this paper, we will always assume graphs to be simple, i.e. graphs with no self-loops such that there can be at most one edge between any (ordered or unordered, depending on whether the graph is directed or not) pair of vertices. Given a graph GG, we use V(G)V(G) and E(G)E(G) to denote, respectively, the set of vertices and the set of edges of GG. We write deg⁡G(v)\deg_G(v) for the degree of a vertex vv in GG, namely the number of neighbors of vv.

A path or walk through a graph GG is a (finite or infinite) sequence of vertices (vn)n(v_n)_n of GG such that, for each nn, the edge {vn,vn+1}\{v_n,v_{n+1}\} (or (vn,vn+1)(v_n,v_{n+1}) in case GG is directed) is in E(G)E(G). Since we are working with simple graphs, a path uniquely identifies a sequence of edges. A trail is a path where no edge is repeated. A finite trail is called closed or open according to whether the initial and final vertices are the same or not. A ray is an infinite or finite and open trail with no repeated vertices. A cycle is a closed (non-empty) trail with at least one edge and no repeated vertices except for its endpoints. An Eulerian path is a trail that uses each edge and goes through each vertex. We distinguish between one-way Eulerian paths, namely Eulerian paths of the form (vn)n∈N(v_n)_{n\in\mathbb{N}} and two-way Eulerian paths, i.e. Eulerian paths of the form (vn)n∈Z(v_n)_{n\in\mathbb{Z}}.

There are well-known results that characterize exactly the graphs that admit Eulerian paths. To state them, we first introduce the following definitions: given a graph GG and a set of edges FF, we define G−FG-F as the graph obtained by removing all edges in FF from GG, as well as every vertex that remains isolated after the removal of FF. In symbols:

E(G−F):=E(G)∖F,E(G-F) := E(G) \setminus F,
V(G−F):=V(G)∖{v∈V(G):v is isolated in (V(G),E(G−F))}.V(G-F) := V(G) \setminus\{v \in V(G) : v\text{ is isolated in }(V(G),E(G-F))\}.

Theorem 2.1 (Erdős-Grünwald-Weiszfeld [15 Thm. 3.2.1]). A countable graph GG has an infinite one-way undirected Eulerian path iff

  1. GG is connected,

  2. GG has at most one odd-degree vertex, and if it has none then it has at least one infinite-degree vertex,

  3. for every finite set of edges F⊆E(G)F \subseteq E(G), G−FG-F has exactly one infinite connected component.

The characterization for directed graphs requires distinguishing whether an edge incident to a vertex vv is incoming, namely it is of the form (u,v)(u,v) for some vertex uu, or outgoing, namely it is of the form (v,u)(v,u) for some vertex uu. We write in⁡D(v)\operatorname{in}_D(v) and out⁡D(v)\operatorname{out}_D(v) for the number of incoming and outgoing edges at vv, respectively.

We say that a directed graph DD is weakly unbiased if, for every X⊆V(D)X \subseteq V(D), the set of edges entering XX is infinite if and only if the set of edges leaving XX is infinite. We say that DD is strongly unbiased1 if it is weakly unbiased and, whenever the sets of edges entering and leaving XX are both finite, their cardinalities differ by at most 1.

For each directed graph DD, we define the underlying undirected graph of DD as the undirected graph HH defined as follows: V(H):=V(D)∪{ξe∈N:e∈E(D)}V(H) := V(D) \cup\{\xi_e \in\mathbb{N} : e \in E(D)\} where we can assume, modulo reindexing the vertices of DD, that every ξe\xi_e is a fresh vertex not in V(D)V(D). The edges of HH are obtained by splitting each edge e∈E(D)e \in E(D) in two using ξe\xi_e and then removing the orientation. In symbols: E(H):=⋃e=(u,v)∈E(D){{u,ξe},{ξe,v}}E(H) := \bigcup_{e=(u,v)\in E(D)} \{\{u,\xi_e\},\{\xi_e,v\}\}. The reason why each edge is first split into two is to retain the fact that DD may contain the edges (u,v)(u,v) and (v,u)(v,u), hence removing the direction while preserving the edges would result in a multigraph.

Theorem 2.2 (Nash-Williams [13, Thm. 1]). Let D=(V,E)D = (V,E) be a countable directed graph and let v0∈Vv_0 \in V. Then DD admits a one-way directed Eulerian path starting from v0v_0 iff all the following conditions hold:

  1. The underlying undirected graph of DD admits a one-way (undirected) Eulerian path,

  1. For every vertex v∈Vv \in V,

out⁡D(v)={in⁡D(v)+1if v=v0,in⁡D(v)if v≠v0.\operatorname{out}_D(v) = \begin{cases} \operatorname{in}_D(v) + 1 & \text{if } v = v_0,\\ \operatorname{in}_D(v) & \text{if } v \ne v_0. \end{cases}

with the convention that ∞+1=∞\infty+ 1 = \infty.

  1. DD is weakly unbiased.

We also mention the characterizations of when an undirected/directed graph admits a two-way Eulerian path.

Theorem 2.3 (Erdős-Grünwald-Weiszfeld [15, Thm. 3.2.2]). A countable graph GG has an infinite two-way undirected Eulerian path iff

  1. GG is connected,

  1. GG has no odd-degree vertex,

  1. for every finite set of edges PP, G−PG-P has at most two infinite connected components. Moreover, if for any v∈V(G)v \in V(G), PP contains an even number of edges incident to vv, then G−PG-P has exactly one infinite connected component.

Theorem 2.4 (Nash-Williams [13, Thm. 2]). A countable directed graph D=(V,E)D = (V,E) admits a two-way directed Eulerian path iff all the following conditions hold:

  1. The underlying undirected graph of DD admits a two-way (undirected) Eulerian path,

  1. DD is strongly unbiased.

Observe that the two conditions in the previous theorem imply that, in a directed graph DD with a two-way directed Eulerian path, each vertex vv must satisfy in⁡D(v)=out⁡D(v)\operatorname{in}_D(v) = \operatorname{out}_D(v).

Weihrauch reducibility

We briefly recall the main definitions on Weihrauch reducibility. For a more comprehensive presentation of Weihrauch reducibility, we refer the reader to [5].

Given f,g:⊆NN⇒NNf,g:\subseteq\mathbb{N}^{\mathbb{N}}\Rightarrow\mathbb{N}^{\mathbb{N}}, we say that ff is Weihrauch reducible to gg, and write f≤Wgf\leq_{\mathrm{W}}g, if there are two computable functionals Φ:⊆NN→NN\Phi:\subseteq\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}} and Ψ:⊆NN×NN→NN\Psi:\subseteq\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{\mathbb{N}}\to\mathbb{N}^{\mathbb{N}} such that, for every p∈dom⁡(f)p\in\operatorname{dom}(f),

Φ(p)∈dom⁡(g)∧(∀q∈g(Φ(p)))(Ψ(p,q)∈f(p)).\Phi(p)\in\operatorname{dom}(g)\wedge(\forall q\in g(\Phi(p)))(\Psi(p,q)\in f(p)).

We call Φ\Phi and Ψ\Psi the forward and backward functionals, respectively. These definitions can be extended to multi-valued functions on represented spaces by requiring that both Φ\Phi and Ψ\Psi work on names of the objects. However, spaces like N\mathbb{N}, Z\mathbb{Z}, N<N\mathbb{N}^{<\mathbb{N}}, or (NN)N(\mathbb{N}^{\mathbb{N}})^{\mathbb{N}}, as well as combinatorial objects like graphs or trees, admit a canonical representation as elements of NN\mathbb{N}^{\mathbb{N}}. In these cases, with a small abuse of notation, we can identify an object with its name. In particular, as anticipated in the introduction, a graph G=(V,E)G=(V,E) is identified with the characteristic function of VV and EE. One-way or two-way paths are canonically represented as elements of NN\mathbb{N}^{\mathbb{N}}. We think of N∪{∞}\mathbb{N}\cup\{\infty\} as a discrete space (hence, in terms of representations, it can be identified with N\mathbb{N}).

The Weihrauch degrees form a distributive lattice with a bottom element (∅\emptyset) and no top element. The join and meet operators can be obtained, respectively, by lifting the following two operators on multi-valued functions to the degree structure:

  • (f0⊔f1)(i,x):=fi(x)(f_0\sqcup f_1)(i,x):=f_i(x), where dom⁡(f0⊔f1):=⋃i<2{i}×dom⁡(fi)\operatorname{dom}(f_0\sqcup f_1):=\bigcup_{i<2}\{i\}\times\operatorname{dom}(f_i).

  • (f0⊓f1)(x0,x1):=⋃i<2{i}×fi(xi)(f_0\sqcap f_1)(x_0,x_1):=\bigcup_{i<2}\{i\}\times f_i(x_i), where dom⁡(f0⊓f1):=dom⁡(f0)×dom⁡(f1)\operatorname{dom}(f_0\sqcap f_1):=\operatorname{dom}(f_0)\times\operatorname{dom}(f_1).

The framework of Weihrauch reducibility supports a wide range of operators on computational problems, enabling the study of the uniform computational strength of natural combinations and modifications of existing problems. We briefly introduce the ones that will be relevant for this paper.

The parallel product f×gf\times g is the problem with dom⁡(f×g):=dom⁡(f)×dom⁡(g)\operatorname{dom}(f\times g):=\operatorname{dom}(f)\times\operatorname{dom}(g) defined as f×g(x,y):=f(x)×g(y)f\times g(x,y):=f(x)\times g(y). It corresponds to the idea of being able to use both ff and gg in parallel. The parallel product can be generalized to the countable case: we define the parallelization f^\widehat{f} of a problem ff as the problem whose domain is the set of sequences (xn)n∈N(x_n)_{n\in\mathbb{N}} of elements in dom⁡(f)\operatorname{dom}(f) and f^((xn)n∈N):=∏n∈Nf(xn)\widehat{f}((x_n)_{n\in\mathbb{N}}):=\prod_{n\in\mathbb{N}}f(x_n). To capture the idea of using ff and gg in series, we introduce the compositional product f∗gf*g as follows: let (Γw)w∈NN(\Gamma_w)_{w\in\mathbb{N}^{\mathbb{N}}} be an effective presentation for all partial continuous functions with Π20\Pi^0_2 domain. We define

dom⁡(f∗g):={(w,x)∈NN×dom⁡(g):(∀y∈g(x))(Γw(y)∈dom⁡(f))};\operatorname{dom}(f*g):=\{(w,x)\in\mathbb{N}^{\mathbb{N}}\times\operatorname{dom}(g):(\forall y\in g(x))(\Gamma_w(y)\in\operatorname{dom}(f))\};
f∗g(w,x):={(z,y):y∈g(x)∧z∈f(Γw(y))}.f*g(w,x):=\{(z,y):y\in g(x)\wedge z\in f(\Gamma_w(y))\}.

The parallel product, parallelization, and compositional product lift to Weihrauch degrees. There are also many natural operators that are not degree-theoretic. The jump2{}^{2} of a problem ff is the problem f′f' whose input is a sequence (pn)n∈N(p_n)_{n\in\mathbb{N}} in NN\mathbb{N}^{\mathbb{N}} converging to some p∈dom⁡(f)p\in\operatorname{dom}(f), and f′((pn)n∈N):=f(p)f'((p_n)_{n\in\mathbb{N}}):=f(p).

For every partial multi-valued function f:⊆NN⇒NNf:\subseteq\mathbb{N}^{\mathbb{N}}\Rightarrow\mathbb{N}^{\mathbb{N}}, its total continuation or totalization ([14]) is the total multi-valued function T(f):NN⇒NN\mathrm{T}(f):\mathbb{N}^{\mathbb{N}}\Rightarrow\mathbb{N}^{\mathbb{N}} defined as

T(f)(x):={f(x)if x∈dom⁡(f),NNotherwise.\mathrm{T}(f)(x):= \begin{cases} f(x) & \text{if }x\in\operatorname{dom}(f),\\ \mathbb{N}^{\mathbb{N}} & \text{otherwise.} \end{cases}

The strong total continuation of ff ([11]) is the total multi-valued function sT⁡(f):NN⇒NN\operatorname{sT}(f):\mathbb{N}^{\mathbb{N}} \Rightarrow\mathbb{N}^{\mathbb{N}} defined as

sT⁡(f)(x):={1⌢f(x)if x∈dom⁡(f),0Notherwise.\operatorname{sT}(f)(x) := \begin{cases} 1 \mathbin{\frown} f(x) & \text{if } x \in\operatorname{dom}(f),\\ 0^{\mathbb{N}} & \text{otherwise.} \end{cases}

The difference between T⁡(f)\operatorname{T}(f) and sT⁡(f)\operatorname{sT}(f) is that an answer for the latter comes with the indication of whether x∈dom⁡(f)x \in\operatorname{dom}(f), whereas this is not the case for the former. Neither of the two operators lifts to the Weihrauch degrees.

When studying the uniform computational strength of problems, it is common to compare them with benchmark problems, whose Weihrauch degree is well-studied and can be used as a reference.

For a metric space XX, lim⁡X\lim_X is the problem that maps a convergent sequence in XX to its limit. We omit the subscript if X=NNX = \mathbb{N}^{\mathbb{N}}. It is well-known that lim⁡2<Wlim⁡N<Wlim⁡\lim_2 <_{\mathrm{W}} \lim_{\mathbb{N}} <_{\mathrm{W}} \lim, where 2={0,1}2 = \{0,1\} is the discrete space with two elements ([4, Thm. 13.5]). A convenient way to use lim⁡\lim is via the equivalence LPO⁡′≡Wlim⁡\operatorname{LPO}' \equiv_{\mathrm{W}} \lim ([5, Thm. 11.6.7]), where LPO⁡:2N→2\operatorname{LPO}:2^{\mathbb{N}} \to2 is defined as LPO⁡(p):=1\operatorname{LPO}(p):=1 iff (∃n)(p(n)=1)(\exists n)(p(n)=1). In other words, LPO⁡\operatorname{LPO} can be used to answer a Σ10\Sigma^0_1 or Π10\Pi^0_1 question, and lim⁡\lim can solve countably many of these questions in parallel. Similarly, the problem LPO⁡′\operatorname{LPO}' can be used to answer a Σ20\Sigma^0_2 or Π20\Pi^0_2 question, and lim⁡<WLPO⁡′≡Wlim⁡′\lim<_{\mathrm{W}} \operatorname{LPO}' \equiv_{\mathrm{W}} \lim' (see e.g. [5, Thm. 11.6.5] and the proof of [16, Thm. 7.2]).

The choice problems are an important family of benchmarks: they intuitively describe the complexity of finding a point in a non-empty set. This complexity depends on the representation and the topological properties of the set. The formal definition of the closed choice problem CXC_X is usually given in the more general context of represented spaces, but for the purposes of this paper, we can give the following (Weihrauch-equivalent) definition: for X={0,…,k−1}X = \{0,\ldots,k-1\} or X=NX = \mathbb{N} the problem CXC_X takes as input a non-empty A⊆XA \subseteq X represented by a Π10\Pi^0_1 formula (i.e. the input is a relation R⊆N×XR \subseteq\mathbb{N} \times X such that n∈An \in A iff, for all i∈Ni \in\mathbb{N}, (i,n)∈R(i,n) \in R), and produces n∈An \in A. It is known that C2<WC3<WCNC_2 <_{\mathrm{W}} C_3 <_{\mathrm{W}} C_{\mathbb{N}} (see e.g. [5, Prop. 11.7.18]).

The problem CNC_{\mathbb{N}} is particularly important as being reducible to CN≡Wlim⁡NC_{\mathbb{N}} \equiv_{\mathrm{W}} \lim_{\mathbb{N}} ([5, Thm. 11.7.13]) corresponds to being computable with finitely many mind-changes [5 Prop. 11.6.1]. It is known that CN^≡Wlim⁡\widehat{C_{\mathbb{N}}} \equiv_{\mathrm{W}} \lim [5 Thm. 11.6.7]. In comparison, C2C_2 is significantly weaker, as C2^\widehat{C_2} is Weihrauch-equivalent to weak König’s lemma, namely the problem of finding a path in an infinite tree T⊆2<NT \subseteq2^{<\mathbb{N}}. We will be especially interested in the problems C2′C'_2 and CN′C'_{\mathbb{N}}. A convenient way to describe them is the following: for X=2X = 2 or X=NX = \mathbb{N}, CX′C'_X is the problem that takes as input a non-empty A⊆XA \subseteq X defined by a Π20\Pi^0_2 formula, and produces n∈An \in A. It is known that C2′C'_2 is Weihrauch-equivalent to the pigeonhole principle RT⁡21\operatorname{RT}^1_2 for singletons and two colors (see [6, Fact 2.3 and Prop. 3.4]).

Finally, we introduce the problem Sort⁡2:2N→2N\operatorname{Sort}_2:2^{\mathbb{N}} \to2^{\mathbb{N}} defined as

Sort⁡2(p):={0n1ωif p contains exactly n zeroes0ωotherwise.\operatorname{Sort}_2(p) := \begin{cases} 0^n1^\omega& \text{if } p \text{ contains exactly } n \text{ zeroes}\\ 0^\omega& \text{otherwise.} \end{cases}

This will be useful to obtain an upper bound for the problem OrientEP⁡\operatorname{OrientEP} (see Definition 4.1 below). It is known that CN<WSort⁡2<Wlim⁡C_{\mathbb{N}} <_{\mathrm{W}} \operatorname{Sort}_2 <_{\mathrm{W}} \lim ([14, Prop. 24]).

Some results

We conclude this section with a few observations explaining why the techniques available in the literature do not directly yield a characterization of the uniform computational strength of finding an Eulerian path.

As mentioned in the introduction, every highly recursive or moderately computable graph that admits a (one-way or two-way) Eulerian path has a computable such path ([3, Thms. 2 and 3] and [7, Thm. A]). In fact, both results relativize to GG and the degree function dG:v↦deg⁡G(v)d_G:v \mapsto\deg_G(v). We also observe that Theorems 2 and 3 in [3] are uniform constructions, whereas the one-way case in [7 Thm. A] requires the additional knowledge of whether the graph has an odd-degree vertex.

Let Deg⁡\operatorname{Deg} be the function that takes as input a graph G=(V,E)G=(V,E) and a vertex v∈Vv\in V and returns deg⁡G(v)\operatorname{deg}_{G}(v). Let also Deg⁡LF\operatorname{Deg}_{\mathrm{LF}} be the restriction of Deg⁡\operatorname{Deg} to locally finite graphs.

Proposition 2.5. Deg⁡LF≡WCN<WDeg⁡≡WsTCN\operatorname{Deg}_{\mathrm{LF}}\equiv_{\mathrm{W}}\mathrm{CN}<_{\mathrm{W}}\operatorname{Deg}\equiv_{\mathrm{W}}\mathrm{sTC}_{\mathbb{N}}.

Proof. To show that Deg⁡LF≤WCN\operatorname{Deg}_{\mathrm{LF}}\le_{\mathrm{W}}\mathrm{CN} and Deg⁡≤WsTCN\operatorname{Deg}\le_{\mathrm{W}}\mathrm{sTC}_{\mathbb{N}} we proceed as follows: for any graph G=(V,E)G=(V,E) and any vertex v∈Vv\in V, first compute an enumeration (vn)n∈N(v_n)_{n\in\mathbb{N}} of VV (possibly with repetitions). Then, we can build the set

A:={b∈N:(∀u∈V)({v,u}∈E⇒(∃n≤b)(u=vn))}.A:=\{b\in\mathbb{N}:(\forall u\in V)(\{v,u\}\in E\mathbin{\Rightarrow}(\exists n\le b)(u=v_n))\}.

Observe that if deg⁡G(v)<∞\operatorname{deg}_{G}(v)<\infty (which is always the case if GG is locally finite), then A≠∅A\ne\varnothing, hence we can use CN\mathrm{CN} to pick a point b∈Ab\in A. Given such a bound bb, we can compute deg⁡G(v)\operatorname{deg}_{G}(v) by computing the size of {u∈V:(∃n≤b)(u=vn)∧{u,v}∈E}\{u\in V:(\exists n\le b)(u=v_n)\land\{u,v\}\in E\}. Conversely, if deg⁡G(v)=∞\operatorname{deg}_{G}(v)=\infty then A=∅A=\varnothing. In this case, the answer of sTCN\mathrm{sTC}_{\mathbb{N}} contains the information that AA is empty, which implies that deg⁡G(v)=∞\operatorname{deg}_{G}(v)=\infty.

To prove the reductions CN≤WDeg⁡LF\mathrm{CN}\le_{\mathrm{W}}\operatorname{Deg}_{\mathrm{LF}} and sTCN≤WDeg⁡\mathrm{sTC}_{\mathbb{N}}\le_{\mathrm{W}}\operatorname{Deg} observe that, given A⊆NA\subseteq\mathbb{N}, we can compute the function g:N→Ng:\mathbb{N}\to\mathbb{N} mapping ss to the least number not enumerated outside of AA by stage ss. We can build a graph GG on N\mathbb{N} whose edges are all and only those of the form {0,s+1}\{0,s+1\} where ss is such that g(s+1)≠g(s)g(s+1)\ne g(s). Observe that A≠∅A\ne\varnothing iff gg is eventually constant with value min⁡A\min A iff deg⁡G(0)\operatorname{deg}_{G}(0) is finite. Besides, deg⁡G(0)\operatorname{deg}_{G}(0) counts the changes of gg, so, if this is a finite number, then it allows us to compute min⁡A\min A.

Finally, it is known that CN<WsTCN\mathrm{CN}<_{\mathrm{W}}\mathrm{sTC}_{\mathbb{N}} as CN^≡Wlim⁡<Wlim⁡′≡WsTC^N\widehat{\mathrm{CN}}\equiv_{\mathrm{W}}\lim<_{\mathrm{W}}\lim'\equiv_{\mathrm{W}}\widehat{\mathrm{sTC}}_{\mathbb{N}} (the last equivalence follows e.g. from [16 Thm. 7.12]).

The above proposition can be adapted so that, in the proof of the reductions CN≤WDeg⁡LF\mathrm{CN}\le_{\mathrm{W}}\operatorname{Deg}_{\mathrm{LF}} and sTCN≤WDeg⁡\mathrm{sTC}_{\mathbb{N}}\le_{\mathrm{W}}\operatorname{Deg}, we always build a graph GG that admits a one-way or two-way Eulerian path.

Corollary 2.6. The restriction of EP\mathrm{EP} to locally finite graphs is Weihrauch-equivalent to lim⁡\lim.

Proof. For the upper bound, let G=(V,E)G=(V,E) be a locally finite graph admitting a one-way Eulerian path. In light of [3 Thm. 2], in order to compute an Eulerian path through a given locally finite graph, it is enough to compute the function d:V→Nd:V\to\mathbb{N} mapping every vertex to its degree. By the previous proposition, this can be done uniformly using lim⁡\lim.

The converse reduction is implicit in the direction (3) ⇒\Rightarrow (1) of the proof of [10 Thm. 12].

With minor modifications, the above arguments can be adapted to the case of directed graphs. In fact, Proposition 2.5 can be adapted to show that the map (D,v)↦in⁡D(v)(D,v)\mapsto\operatorname{in}_{D}(v) is Weihrauch-equivalent to CN\mathrm{CN} if each vertex has a finite number of incoming edges, and it is Weihrauch-equivalent to sTCN\mathrm{sTC}_{\mathbb{N}} in the general case. An analogous characterization holds for the map (D,v)↦out⁡D(v)(D,v)\mapsto\operatorname{out}_{D}(v). In particular, knowing that for every D∈dom⁡(DEP)D\in\operatorname{dom}(\mathrm{DEP}) and every v∈V(D)v\in V(D), in⁡D(v)\operatorname{in}_{D}(v) is finite iff out⁡D(v)\operatorname{out}_{D}(v) is finite, we obtain that the restriction of DEP\mathrm{DEP} to locally finite graphs is Weihrauch-equivalent to lim⁡\lim.

These observations show that any approach to bounding the uniform computational strength of EP\mathrm{EP} or DEP\mathrm{DEP} that begins by computing the degree function (or both the in-degree and out-degree functions in case of directed graphs) would yield an upper bound at the level of lim⁡′\lim' (or above). In light of the rest of the paper, such an upper bound would not be optimal.

Similar considerations apply to the case of two-way undirected Eulerian paths. Indeed, as noted in [10 Sec. 3], the argument for the one-way Eulerian paths can be adapted to two-way undirected Eulerian paths. An analogous argument for two-way directed Eulerian paths does not seem to have been explicitly presented in the literature.

One-way Eulerian paths

For the sake of readability, we split the characterization of the Weihrauch degree of EP and DEP as follows: we first show the lower bound (Lemma 3.1). Then, for the upper bound, we show that starting from a prescribed vertex simplifies the problem of finding a one-way (directed or undirected) Eulerian path (Theorem 3.2). These facts, together with a technical lemma (Lemma 3.3) are then combined in the proof of Theorem 3.4.

Lemma 3.1. lim⁡×CN′≤WEP\lim\times\mathrm{C}_{\mathbb{N}}' \leq_{\mathrm{W}} \mathrm{EP} and lim⁡×CN′≤WDEP\lim\times\mathrm{C}_{\mathbb{N}}' \leq_{\mathrm{W}} \mathrm{DEP}.

Proof. We only show that lim⁡×CN′≤WDEP\lim\times\mathrm{C}_{\mathbb{N}}' \leq_{\mathrm{W}} \mathrm{DEP}. The reduction to EP builds the same graph, with the only difference being that the edges are undirected.

Let (pn)n∈N(p_n)_{n\in\mathbb{N}} be an input for LPO′\mathrm{LPO}^{\prime} (≡Wlim⁡\equiv_{\mathrm{W}} \lim) and A≠∅A \ne\varnothing be a Π20\Pi^0_2 subset of N\mathbb{N}. We represent AA as a sequence (qn)n∈N(q_n)_{n\in\mathbb{N}} in 2N2^{\mathbb{N}} such that n∈A⟺(∃∞i)(qn(i)=1)n \in A \Longleftrightarrow(\exists^\infty i)(q_n(i)=1).

We define a graph D=(V,E)D=(V,E) as follows (see Figure 1). We use disjoint computable sets of labels for the backbone, the vertices hnh_n, and auxiliary vertices. The graph has a ray-like backbone b0,b1,…b_0,b_1,\ldots where every backbone vertex bib_i is connected to bi+1b_{i+1} via two paths of length 2 going in opposite directions.

Figure 1. The construction of the directed graph DD.

We will attach two different types of gadgets to this backbone. One will help us decide each LPO instance and the other will give us a solution to CN′(A)\mathrm{C}_{\mathbb{N}}'(A).

The first one is (essentially) the same gadget used in [10 Thm. 12]: when we first see that pe(s)=1p_e(s)=1 for some ss, we pick two fresh indexes ueu_e and vev_e and attach a triangle to b2e+1b_{2e+1}, oriented as b2e+1→ue→ve→b2e+1b_{2e+1}\to u_e\to v_e\to b_{2e+1}.

To solve the CN′\mathrm{C}_{\mathbb{N}}'-instance, for each nn we define a dedicated vertex hnh_n (we choose hnh_n so that, knowing hnh_n, we can uniformly compute nn) and attach it to a sufficiently large even backbone vertex unused so far by a triangle hn→cn,j→b2k→hnh_n\to c_{n,j}\to b_{2k}\to h_n, where each cn,jc_{n,j} is new. Whenever we find a new ii such that qn(i)=1q_n(i)=1, we add another such triangle, using a fresh auxiliary vertex cn,jc_{n,j} and a sufficiently large backbone vertex b2kb_{2k} not used by any hmh_m so far. Notice that in⁡D(hn)=out⁡D(hn)=∞\operatorname{in}_D(h_n)=\operatorname{out}_D(h_n)=\infty iff n∈An\in A.

Let us now show that DD admits a one-way directed Eulerian path. Let GG be the underlying undirected graph of DD. Observe that deg⁡G(v)=∞\deg_G(v)=\infty iff v∈{hn:n∈A}v\in\{h_n:n\in A\}, and otherwise it has even degree. In fact, for every v∈V(D)v\in V(D), in⁡D(v)=out⁡D(v)\operatorname{in}_D(v)=\operatorname{out}_D(v). Besides, the fact that A≠∅A\ne\varnothing guarantees that at least one infinite-degree vertex exists. Observe also that deleting any finite set F⊆E(G)F\subseteq E(G) of edges leaves GG with exactly one infinite component: indeed, for a sufficiently large backbone vertex bb, the backbone tail beyond bb remains connected, and each backbone vertex before bb can have at most 1 triangle attached (whether a connection to some hnh_n or a witness for the ee-th LPO instance). By Theorem 2.1, this shows that GG admits a one-way Eulerian path. It remains to show that DD is weakly unbiased. Observe first that its edges can be partitioned into finite directed cycles (either triangles or diamonds). For every X⊆V(D)X \subseteq V(D), each such cycle has equally many edges entering and leaving XX. Summing over the cycles shows that the sets of edges entering and leaving XX have the same cardinality, hence DD is weakly unbiased. In particular, for every n∈An \in A, Theorem 2.2 implies that there is a one-way directed Eulerian path through DD starting from hnh_n.

Let P∈DEP⁡(D)P \in\operatorname{DEP}(D) be a one-way Eulerian path through DD. Since every vertex has the same incoming and outgoing degree, P(0)=hnP(0) = h_n for some n∈An \in A. This is because the starting vertex of the path must satisfy in⁡D(P(0))+1=out⁡D(P(0))\operatorname{in}_D(P(0)) + 1 = \operatorname{out}_D(P(0)). Therefore knowing P(0)P(0) lets us uniformly compute an answer for CN′(A)C'_{\mathbb{N}}(A).

To decide whether LPO⁡(pe)=1\operatorname{LPO}(p_e) = 1, we wait until PP has traversed all four backbone edges incident to b2e+1b_{2e+1}. Then LPO⁡(pe)=1\operatorname{LPO}(p_e) = 1 iff the path traverses the triangle b2e+1→ue→ve→b2e+1b_{2e+1} \to u_e \to v_e \to b_{2e+1}. Indeed, the existence of such triangle implies that we have found ss such that pe(s)=1p_e(s) = 1. Conversely, if the path does not traverse the triangle, it means it has never been added: if the triangle is added to the graph but not traversed after visiting the four edges of b2e+1b_{2e+1} then it would be disconnected from the rest of the graph, hence unreachable, against the fact that PP is an Eulerian path. This shows that we can uniformly compute the answer to every LPO-instance, and therefore conclude the proof. □

Observe that, in the previous argument, the answer to the CN′C'_{\mathbb{N}}-instance is determined solely by the initial vertex of the Eulerian path. This is no coincidence: the next result shows that specifying a valid starting vertex leaves a problem solvable using lim⁡\lim alone.

Theorem 3.2. Let EP⁡start\operatorname{EP}_{\mathrm{start}} (resp. DEP⁡start\operatorname{DEP}_{\mathrm{start}}) be the problem that takes as input a pair (G,v)(G,v), where G=(V,E)G = (V,E) is an undirected (resp. directed) graph, v∈Vv \in V, and GG admits a one-way Eulerian path starting from vv, and returns a one-way undirected (resp. directed) Eulerian path through GG starting from vv. Then

EP⁡start≡WDEP⁡start≡Wlim⁡.\operatorname{EP}_{\mathrm{start}} \equiv_{\mathrm{W}} \operatorname{DEP}_{\mathrm{start}} \equiv_{\mathrm{W}} \lim.

Proof. The reductions lim⁡≤WEP⁡start\lim\leq_{\mathrm{W}} \operatorname{EP}_{\mathrm{start}} and lim⁡≤WDEP⁡start\lim\leq_{\mathrm{W}} \operatorname{DEP}_{\mathrm{start}} can be obtained by simplifying the construction in the proof of Lemma 3.1 as follows (see Figure 2): given an instance (pn)n∈N(p_n)_{n \in\mathbb{N}} for LPO, define a directed graph DD so that it contains a ray b0→b1→b2…b_0 \to b_1 \to b_2 \ldots (we connect bib_i and bi+1b_{i+1} directly instead of via a diamond) and, when we first see that pep_e contains a 1, we add a triangle be→ue→ve→beb_e \to u_e \to v_e \to b_e, for some nodes ue,veu_e,v_e with sufficiently large index. The construction is the same in the undirected case: simply remove the orientation of the edges.

Construction of the reduction lim ≤W DEPstart

Figure 2. The construction for the reduction lim⁡≤WDEP⁡start\lim\leq_{\mathrm{W}} \operatorname{DEP}_{\mathrm{start}}.

It is apparent that DD admits a one-way Eulerian path starting from b0b_0. Besides, we can find the solution to LPO⁡(pe)\operatorname{LPO}(p_e) by checking if the path P∈DEP⁡start(D,b0)P \in\operatorname{DEP}_{\mathrm{start}}(D,b_0) visits be+1b_{e+1} immediately after beb_e or if it instead visits the triangle be→ue→ve→beb_e \to u_e \to v_e \to b_e first.

Let us now show that EP⁡start≤Wlim⁡\operatorname{EP}_{\mathrm{start}} \leq_{\mathrm{W}} \lim. Let (G,v0)∈dom⁡(EP⁡start)(G,v_0) \in\operatorname{dom}(\operatorname{EP}_{\mathrm{start}}). As a consequence of Theorem 2.1, a finite trail σ\sigma starting at v0v_0 is extendible to a one-way Eulerian path iff the final vertex of σ\sigma has an unused incident edge and G−E(σ)G - E(\sigma) is connected (see [7 Thm. 3]). We show that these two conditions are uniformly Δ20\Delta^0_2 relative to σ\sigma and GG, hence we can use lim⁡\lim to check them in parallel for every σ\sigma. Fix a finite trail σ\sigma and assume without loss of generality that ∣σ∣≥2|\sigma| \geq2. Checking if w:=σ(∣σ∣−1)w := \sigma(|\sigma| - 1) has an unused incident edge in G−E(σ)G - E(\sigma) is clearly Σ10\Sigma^0_1 relative to σ\sigma and EE. For the second condition, let

Bσ:={b∈ran⁡(σ):(∃x∈V(G))({x,b}∈E(G)∖E(σ))}B_\sigma:= \{b \in\operatorname{ran}(\sigma) : (\exists x \in V(G))(\{x,b\} \in E(G) \setminus E(\sigma))\}

be the set of vertices in σ\sigma that are the endpoints of some edge not in E(σ)E(\sigma). Since GG is connected, every connected component of G−E(σ)G-E(\sigma) contains a vertex in BσB_\sigma. In particular, G−E(σ)G-E(\sigma) is connected iff BσB_\sigma is connected in G−E(σ)G-E(\sigma). Since BσB_\sigma is Σ10\Sigma^0_1, the latter condition is Δ20\Delta^0_2 relative to σ\sigma and GG.

Using lim⁡\lim, we can then uniformly compute a one-way Eulerian path through GG inductively by unbounded search: fix an enumeration (en)n∈N(e_n)_{n\in\mathbb{N}} of E(G)E(G) and let σ0:=(v0)\sigma_0 := (v_0). At each stage ss, we search for some finite trail σs+1⊒σs\sigma_{s+1} \sqsupseteq\sigma_s that is extendible to an Eulerian path and that visits ese_s. By the inductive hypothesis, such σs+1\sigma_{s+1} exists and the information given to us by lim⁡\lim allows us to find one. The limit of (σs)s∈N(\sigma_s)_{s\in\mathbb{N}} gives us a one-way Eulerian path through GG.

The proof of DEPstart≤Wlim⁡\mathrm{DEP}_{\mathrm{start}} \leq_{\mathrm{W}} \lim follows a similar strategy: let (D,v0)(D,v_0) be an instance of DEPstart\mathrm{DEP}_{\mathrm{start}}. Using Nash-Williams’s theorem (Theorem 2.2), we can show that a finite directed trail σ\sigma starting from v0v_0 is extendible iff

  • the final vertex w:=σ(∣σ∣−1)w := \sigma(|\sigma|-1) has an unused outgoing edge and

  • the underlying undirected graph of H:=D−E(σ)H := D-E(\sigma) is connected.

Clearly, both conditions are necessary. To see that they are sufficient, observe that they imply that the underlying undirected graph of HH has a one-way Eulerian path (as above) and removing finitely many edges preserves weak unbiasedness. Since σ\sigma is a directed trail, for every vertex v≠v0,wv \neq v_0,w there is kk such that out⁡D(v)=out⁡H(v)+k\operatorname{out}_D(v) = \operatorname{out}_H(v) + k and in⁡D(v)=in⁡H(v)+k\operatorname{in}_D(v) = \operatorname{in}_H(v) + k. The same holds for v0v_0 if v0=wv_0 = w (hence, in particular, we obtain out⁡H(w)=in⁡H(w)+1\operatorname{out}_H(w) = \operatorname{in}_H(w) + 1). Otherwise, out⁡H(v0)=in⁡H(v0)\operatorname{out}_H(v_0) = \operatorname{in}_H(v_0) (as the first edge goes out of v0v_0 but there is no previous edge going to v0v_0) and

out⁡D(w)=out⁡H(w)+kandin⁡D(w)=in⁡H(w)+k+1.\operatorname{out}_D(w) = \operatorname{out}_H(w) + k \qquad\text{and}\qquad\operatorname{in}_D(w) = \operatorname{in}_H(w) + k + 1.

This shows that HH and ww satisfy the hypotheses of Theorem 2.2 and hence HH admits a directed one-way Eulerian path starting at ww.

The rest of the proof follows as in the undirected case: the two conditions above are uniformly Δ20\Delta^0_2 relative to σ\sigma and DD, hence we can use lim⁡\lim to check them in parallel for every σ\sigma. Then, we can uniformly compute a directed one-way Eulerian path through DD starting from v0v_0 proceeding inductively by unbounded search while ensuring that we visit each edge.

Lemma 3.3. For every problem gg with codomain N\mathbb{N}, lim⁡∗g≡Wlim⁡×g\lim* g \equiv_{\mathrm{W}} \lim\times g.

Proof. Without loss of generality, assume g:⊆NN⇉Ng :\subseteq\mathbb{N}^{\mathbb{N}} \rightrightarrows\mathbb{N}. The reduction lim⁡×g≤Wlim⁡∗g\lim\times g \leq_{\mathrm{W}} \lim* g is immediate ([5 Prop. 11.5.7]), hence we only need to show the converse reduction. Let (w,x)∈NN×NN(w,x) \in\mathbb{N}^{\mathbb{N}} \times\mathbb{N}^{\mathbb{N}} be a valid input for lim⁡∗g\lim* g. We show that we can solve it using LPO^×g\widehat{\mathrm{LPO}} \times g. We use the ⟨i,j,s⟩\langle i,j,s\rangle-th instance of LPO\mathrm{LPO} to check if there is t>st > s such that, in tt steps, Γw(i)\Gamma_w(i) produces a prefix of a sequence (pn)n∈N(p_n)_{n\in\mathbb{N}} such that for some s≤ts \leq t, ps(j)≠pm(j)p_s(j) \neq p_m(j).

Notice Γw(i)\Gamma_w(i) need not produce a convergent sequence if i∉g(x)i \notin g(x). On the other hand, if i∈g(x)i \in g(x) then Γw(i)=(pn)n∈N∈dom⁡(lim⁡)\Gamma_w(i) = (p_n)_{n\in\mathbb{N}} \in\operatorname{dom}(\lim) and, for every jj there is ss such that (pn(j))n∈N(p_n(j))_{n\in\mathbb{N}} stabilizes after stage ss. In particular, knowing some solution ii for g(x)g(x), we can uniformly compute lim⁡(Γw(i))\lim(\Gamma_w(i)) by searching, for each jj, for the first ss such that the ⟨i,j,s⟩\langle i,j,s\rangle-th instance of LPO\mathrm{LPO} returns 00.

We are now ready to characterize the Weihrauch-degree of EP and DEP.

Theorem 3.4. EP≡WDEP≡Wlim⁡×CN′\mathrm{EP} \equiv_{\mathrm{W}} \mathrm{DEP} \equiv_{\mathrm{W}} \lim\times\mathrm{C}'_{\mathbb{N}}.

Proof. The fact that lim⁡×CN′\lim\times\mathrm{C}'_{\mathbb{N}} is a lower bound for both problems is given by Lemma 3.1. The two reductions EP≤Wlim⁡×CN′\mathrm{EP} \leq_{\mathrm{W}} \lim\times\mathrm{C}'_{\mathbb{N}} and DEP≤Wlim⁡×CN′\mathrm{DEP} \leq_{\mathrm{W}} \lim\times\mathrm{C}'_{\mathbb{N}} follow a similar strategy: we first use CN′≡WCN′∗LPO′\mathrm{C}'_{\mathbb{N}} \equiv_{\mathrm{W}} \mathrm{C}'_{\mathbb{N}} * \mathrm{LPO}' (as it is known that LPO′≤WCN′\mathrm{LPO}' \leq_{\mathrm{W}} \mathrm{C}'_{\mathbb{N}} and CN′\mathrm{C}'_{\mathbb{N}} is closed under compositional product ([5, Thm. 11.7.53(1)})) to find a starting vertex for a (one-way) Eulerian path. We then use lim⁡\lim to obtain the rest of the path (using Theorem 3.2). This shows that both EP and DEP reduce to lim⁡∗CN′\lim* \mathrm{C}'_{\mathbb{N}}, and the claim follows by Lemma 3.3.

In the undirected case, let G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}). Observe that checking if deg⁡G(v)\deg_G(v) is odd is a uniformly Σ20\Sigma^0_2 condition relative to GG and vv, as it is equivalent to

(∃n∈N)(∃F⊆E,∣F∣=2n+1)(∀e∈E)(e is incident to v⇔e∈F)(\exists n \in\mathbb{N})(\exists F \subseteq E,\lvert F\rvert= 2n+1)(\forall e \in E)(e\text{ is incident to }v \Leftrightarrow e \in F)

If there is a vertex with odd degree, then use CN′C^\prime_{\mathbb{N}} to choose the unique such vertex (as CNC_{\mathbb{N}} suffices to choose an element from a given Σ20\Sigma^0_2 subset of N\mathbb{N}). Otherwise, there must be a vertex with infinite degree, hence we use CN′C^\prime_{\mathbb{N}} to choose from the set of vertices with infinite degree (which is uniformly Π20\Pi^0_2 relative to GG).

In the directed case, let D∈dom⁡(DEP)D \in\operatorname{dom}(\mathrm{DEP}). We can use LPO′\mathrm{LPO}^{\prime} to check if there is a vertex v∈Vv \in V such that out⁡D(v)=in⁡D(v)+1<∞\operatorname{out}_D(v)=\operatorname{in}_D(v)+1<\infty. Indeed, this condition is equivalent to check if there are a vertex vv and two finite sets of edges Fin,Fout⊂EF_{\mathrm{in}},F_{\mathrm{out}}\subset E such that ∣Fout∣=∣Fin∣+1\lvert F_{\mathrm{out}}\rvert=\lvert F_{\mathrm{in}}\rvert+1, and FinF_{\mathrm{in}} (resp. FoutF_{\mathrm{out}}) contains all and only the edges in E(D)E(D) incoming to (resp. outgoing from) vv. In particular, this is uniformly Σ20\Sigma^0_2 relative to DD. If such a vertex exists, we can use CN′C^\prime_{\mathbb{N}} to find it. Otherwise, we can use CN′C^\prime_{\mathbb{N}} to choose from the set of vertices v∈V(D)v \in V(D) such that out⁡D(v)=in⁡D(v)=∞\operatorname{out}_D(v)=\operatorname{in}_D(v)=\infty (which is uniformly Π20\Pi^0_2 relative to DD).

Corollary 3.5. lim⁡′̸≤WEP\lim^{\prime}\not\le_{\mathrm{W}}\mathrm{EP} and lim⁡′̸≤WDEP\lim^{\prime}\not\le_{\mathrm{W}}\mathrm{DEP}.

Proof. Simply follows from the fact that there is a computable instance of lim⁡′\lim^{\prime} whose solution is ∅\varnothing, while every computable instance of lim⁡×CN′≡WEP\lim\times C^\prime_{\mathbb{N}}\equiv_{\mathrm{W}}\mathrm{EP} has a Δ20\Delta^0_2 solution.

Corollary 3.6. Both EP and DEP are closed under parallel product, but not parallelizable nor closed under compositional product.

Proof. Since both lim⁡\lim and CN′C^\prime_{\mathbb{N}} are closed under parallel product, so are EP and DEP. To show that EP and DEP are not closed under parallelization nor compositional product, it is enough to observe that CN′≡Wlim⁡′≡Wlim⁡∗lim⁡C^\prime_{\mathbb{N}}\equiv_{\mathrm{W}}\lim^{\prime}\equiv_{\mathrm{W}}\lim\ast\lim, which can be proved using e.g. [5 Props. 11.6.12 and 11.6.14].

Orienting the edges

Definition 4.1. Let OrientEP be the problem that, given G=(V,E)∈dom⁡(EP)G=(V,E)\in\operatorname{dom}(\mathrm{EP}), returns D=(V,A)∈dom⁡(DEP)D=(V,A)\in\operatorname{dom}(\mathrm{DEP}) such that the map π:A→E:=(v,w)↦{v,w}\pi:A\to E:=(v,w)\mapsto\{v,w\} is a (computable) bijection.

It is not hard to show that OrientEP is not uniformly computable.

Proposition 4.2. lim⁡2≤WOrientEP\lim_2\le_{\mathrm{W}}\mathrm{OrientEP}.

Proof. Let (xn)n∈N(x_n)_{n\in\mathbb{N}} be an instance of lim⁡2\lim_2. We build a graph G=(N,E)G=(\mathbb{N},E) as follows: at stage 0, let l0:=0l_0:=0, r0:=1r_0:=1 and we add the edge {0,1}\{0,1\} to EE. Intuitively, we are building a ray, where the direction of the ray (left or right) is determined by the current element of the input sequence.

At stage n+1n+1, if xn+1=0x_{n+1}=0, we add the edge {n+2,ln}\{n+2,l_n\} and define ln+1:=n+2l_{n+1}:=n+2, rn+1:=rnr_{n+1}:=r_n. Symmetrically, if xn+1=1x_{n+1}=1, we add the edge {n+2,rn}\{n+2,r_n\} and define ln+1:=lnl_{n+1}:=l_n, rn+1:=n+2r_{n+1}:=n+2.

Since the sequence (xn)n∈N(x_n)_{n\in\mathbb{N}} is eventually constant with value ii, exactly one of its values is extended infinitely often, so GG is a ray. The only D∈OrientEP(G)D\in\mathrm{OrientEP}(G) orients {0,1}\{0,1\} as (0,1)(0,1) iff i=1i=1, uniformly computing the limit.

We can obtain the separation OrientEP̸≤Wlim⁡2\mathrm{OrientEP}\not\le_{\mathrm{W}}\lim_2 as a corollary of the next stronger result (as lim⁡2<WCN\lim_2<_{\mathrm{W}}C_{\mathbb{N}}):

Proposition 4.3. OrientEP̸≤WCN\mathrm{OrientEP}\not\le_{\mathrm{W}}C_{\mathbb{N}}. Proof. Assume towards a contradiction that OrientEP⁡≤WCN\operatorname{OrientEP} \leq_W \mathrm{C}_{\mathbb{N}} via the functionals Φ,Ψ\Phi,\Psi. Notice that, for each input AA for CN\mathrm{C}_{\mathbb{N}}, we can uniformly compute a guessing function gA:N→Ng_A:\mathbb{N}\to\mathbb{N} such that, for each ss, gA(s)g_A(s) is the least number not enumerated outside of AA by stage ss. In particular, lim⁡sgA(s)=min⁡A\lim_s g_A(s)=\min A.

To obtain a contradiction, we build a graph GG so as to force the guessing function gΦ(G)g_{\Phi(G)} to not have a limit. The graph GG is built iteratively as follows: at each stage ss, the approximation GsG_s of GG is a graph consisting of a finite number of finite cycles going through the vertex 00 and a finite ray RsR_s containing 00. Let gsg_s be the least number not enumerated outside of Φ(Gs)\Phi(G_s) by stage ss. Without loss of generality, we can assume that, in ss steps, both computations Φ(Gs)\Phi(G_s) and Ψ(Gs,gs)\Psi(G_s,g_s) only query the oracle on edges whose endpoints are at most ss. This is useful so that later changes to the approximation of GG preserve earlier computations.

We start at stage 11 with G1G_1 being the graph with two vertices 00 and 11 connected by an edge. The construction alternates between two different phases. We start in Phase 1.

Phase 1 In this phase, the ray RsR_s is of the form (0,t,t+1,t+2,…,s)(0,t,t+1,t+2,\ldots,s) for some t≤st\leq s. We check if Ψ(Gs,gs)\Psi(G_s,g_s), in ss steps, commits to the orientation of any edge {t+j,t+j+1}\{t+j,t+j+1\} as (t+j,t+j+1)(t+j,t+j+1). If this does not happen, we add the edge {s+1,s}\{s+1,s\}, go to the next stage and remain in Phase 1. Otherwise, we add the edge {s+1,0}\{s+1,0\} and we move to Phase 2 and go to the next stage.

Phase 2 The ray is Rs=(s,…,r,0,t,…,t+k)R_s=(s,\ldots,r,0,t,\ldots,t+k) for some t<t+k<r≤st<t+k<r\leq s. We add the edge {s+1,s}\{s+1,s\}. We also check if Ψ(Gs,gs)\Psi(G_s,g_s), in ss steps, commits to the orientation of any edge {r,r+1}\{r,r+1\} as (r,r+1)(r,r+1). If this does not happen, we go to the next stage and remain in Phase 2. Otherwise, we close the loop by adding the edge {s+1,t+k}\{s+1,t+k\}. We also add the edge {0,s+2}\{0,s+2\}, then move to Phase 1 and go to stage s+2s+2.

The two phases of the construction and the closing of the loop

Figure 3. The two phases of the construction and the closing of the loop. Previously completed loops at 0 are omitted. Arrows on edges indicate the orientations produced by Ψ\Psi.

Observe that the construction must alternate between the two phases infinitely often. Indeed, if from a certain stage ss on, the construction remains in Phase 1, then the resulting graph GG is a ray with finitely many attached cycles (hence G∈dom⁡(EP))G\in\operatorname{dom}(\mathrm{EP})) and the backward functional never orients the edges of the ray away from the origin 00. Clearly, no edge of the ray can be oriented toward 00 (otherwise there cannot be any Eulerian path), hence it means that Ψ\Psi never produces an orientation for any edge of the ray, against the fact that Ψ\Psi witnesses a Weihrauch reduction. The case when the construction remains in Phase 2 is symmetric.

This shows that the resulting graph GG is the union of countably many cycles whose only vertex in common is 00 (which therefore has infinite degree), therefore GG admits an Eulerian path.

To conclude the proof, it is enough to notice that every change from Phase 1 to Phase 2 forces gΦ(G)g_{\Phi(G)} to change guess. Indeed, assume otherwise and let gsg_s be the current guess. When we close the loop, Ψ(G,gs)\Psi(G,g_s) has committed to orienting an edge away from 00 on each of its two sides. Therefore, regardless of how the remaining edges are oriented, there must be a vertex in the loop other than 00 with two incoming edges and no outgoing one. Since this vertex has degree 22 in GG, the resulting directed graph cannot admit an Eulerian path, against the fact that Ψ\Psi witnesses a Weihrauch reduction. Hence the guesses must change infinitely often, contradicting the convergence of gsg_s. □\square

We now work towards producing an upper bound for OrientEP. We will show that OrientEP <WC2′⊓Sort2<_{\mathrm W} \mathrm{C}'_2 \sqcap\mathrm{Sort}_2. To show that OrientEP ≤WC2′\leq_{\mathrm W} \mathrm{C}'_2, we first need the following lemma.

Lemma 4.4. There is a computable procedure that, given a graph G=(V,E)∈dom⁡(EP)G=(V,E)\in\operatorname{dom}(\mathrm{EP}), computes a directed graph D=(V,A)D=(V,A) by choosing an orientation of the edges in EE such that either D∈dom⁡(DEP)D\in\operatorname{dom}(\mathrm{DEP}) or Dop:=(V,Aop)∈dom⁡(DEP)D^{\mathrm{op}}:=(V,A^{\mathrm{op}})\in\operatorname{dom}(\mathrm{DEP}).

Proof. The idea is to orient the graph locally, partitioning its edges into finite directed closed trails and at most one remaining directed trail (which could be finite, one-way infinite, or two-way infinite). The hypothesis that GG admits a one-way Eulerian path guarantees that the searches in the construction succeed. We will then show that the resulting orientation is weakly unbiased and that every vertex is balanced, with the possible exception of the unique odd-degree vertex of GG. If there is such a vertex vv, the correct global direction is the one satisfying in⁡D(v)+1=out⁡D(v)\operatorname{in}_D(v)+1=\operatorname{out}_D(v); otherwise, both DD and DopD^{\mathrm{op}} will admit a one-way directed Eulerian path.

We now show how to define the orientation AA (which yields the directed graph DD). Let (en)n∈N(e_n)_{n\in\mathbb{N}} be an enumeration of EE. At each step, we maintain a finite directed open trail τs\tau_s, which we aim to extend at either endpoint. Start with τ0\tau_0 being an arbitrary orientation of e0e_0. At stage ss, let ene_n be the least unoriented edge yet. We search for a finite directed trail ρ\rho that only includes unoriented edges and that satisfies one of the following:

  1. ρ\rho includes ene_n and is a closed trail edge-disjoint from τs\tau_s;

  2. ρ\rho includes ene_n and can be prepended or appended to τs\tau_s to form an open directed trail;

  3. ρ\rho can be appended to τs\tau_s to form a closed trail.

In case (1), ρ\rho defines an orientation of its edges. We define τs+1:=τs\tau_{s+1}:=\tau_s and go to the next stage. Similarly, in case (2), we define ϑ\vartheta as the directed trail obtained by prepending or appending ρ\rho to τs\tau_s. Then, we define τs+1:=ϑ\tau_{s+1}:=\vartheta and go to the next stage. Finally, in case (3), we have obtained a closed directed trail. As in (1), we orient the mentioned edges as specified by the obtained closed trail. Then, we define τs+1:=(xm,ym)\tau_{s+1}:=(x_m,y_m), where em={xm,ym}e_m=\{x_m,y_m\} is the first edge not oriented so far, and go to the next stage.

We now show that the search succeeds. Suppose that, at stage ss, none of (1), (2), or (3) is possible. Let u:=τs(0)u:=\tau_s(0) and w:=τs(∣τs∣−1)w:=\tau_s(|\tau_s|-1). Let H:=(V(G),Es)H:=(V(G),E_s), where EsE_s is the set of edges not oriented by stage ss. Observe that committing to the orientation of a finite closed trail preserves the degree parity of each vertex. Similarly, the degree parity is preserved for every vertex in τs\tau_s different from u,wu,w. In symbols:

(∀v∈V∖{u,w})(∃k∈N)(deg⁡G(v)=deg⁡H(v)+2k).(\forall v\in V\setminus\{u,w\})(\exists k\in\mathbb{N})(\deg_G(v)=\deg_H(v)+2k).

Let KK be the connected component of HH containing ene_n.

The failure of (2) and (3) implies that KK contains neither uu nor ww. Besides, the failure of (1) implies that KK is infinite. Indeed, recall that GG can have at most one odd-degree vertex. If KK were finite then all of its vertices would have even degree, since the sum of the degrees of vertices in a finite graph is always even3^{3}. In particular, KK would admit a closed Eulerian trail [15 Thm. 3.11]. Such a trail, once oriented, would contradict the failure of (1).

By Theorem 2.1, KK is the unique infinite connected component of HH. Let KuK_u and KwK_w be the connected components in HH of uu and ww respectively. In particular Ku≠K≠KwK_u\ne K\ne K_w. Assume towards a contradiction that Ku≠KwK_u\ne K_w. Within KuK_u, deleting the already oriented edges changes degree parity only at uu. Since the finite graph KuK_u has an even number of odd-degree vertices, an odd number of its vertices must have odd degree in GG. In particular, KuK_u contains an odd-degree vertex of GG. The same argument applies to KwK_w, giving two distinct odd-degree vertices of GG, a contradiction. This shows that Ku=KwK_u=K_w and therefore (3) can be satisfied, which is a contradiction.

Since each stage ss of the construction is well-defined, every edge is eventually oriented. The construction yields an edge-decomposition of the resulting graph DD into a family {Ci}i\{C_i\}_i of finite directed closed trails and at most one remaining directed trail RR, which may be finite, one-way infinite, or two-way infinite.

We now show that either DD or DopD^{\mathrm{op}} admits a one-way directed Eulerian path. Observe that each closed directed trail CiC_i contributes equally to the in-degree and out-degree of each vertex. The same holds for every vertex in RR different from the endpoint(s). At each endpoint, the contributions of RR differ by one, so any finite-degree endpoint has odd degree in GG, while every infinite-degree vertex has infinite in-degree and out-degree.

To show that DD (and hence DopD^{\mathrm{op}}) is weakly unbiased, fix X⊆VX \subseteq V. Each closed directed trail CiC_i has equally many edges entering and leaving XX, since either CiC_i is contained in XX or CiC_i is contained in V∖XV \setminus X, or every entrance in XX is followed by an exit. Likewise, along RR, the edges entering and leaving XX alternate: indeed, assume RR is infinite (otherwise it does not affect weak unbiasedness) and one-way. If the tail of RR is contained in XX or in V∖XV \setminus X, then the set of edges of RR that enter and leave XX are finite. Otherwise, XX divides RR in infinitely many finite directed trails RiR_i, each one being a maximal consecutive subtrail of RR entirely contained in XX or in V∖XV \setminus X. Each Ri≠R0R_i \ne R_0 has an incident edge entering XX and an incident edge leaving XX (R0R_0 is an exception as it only has an incident edge leaving XX or has an incident edge entering XX), hence they do not affect the weak unbiasedness of DD. The case when RR is a two-way directed trail is analogous. This shows that both DD and DopD^{\mathrm{op}} are weakly unbiased.

If GG has no odd-degree vertex, both orientations satisfy Theorem 2.2, starting at any infinite-degree vertex. Otherwise, there is v0∈Vv_0 \in V such that deg⁡G(v0)\deg_G(v_0) is odd. Then in⁡D(v0)=out⁡Dop(v0)\operatorname{in}_D(v_0) = \operatorname{out}_{D^{\mathrm{op}}}(v_0) and out⁡D(v0)=in⁡Dop(v0)\operatorname{out}_D(v_0) = \operatorname{in}_{D^{\mathrm{op}}}(v_0). In particular, exactly one of DD and DopD^{\mathrm{op}} satisfies Theorem 2.2 starting at v0v_0.

Theorem 4.5. OrientEP⁡≤WC2′\operatorname{OrientEP} \leq_{\mathrm{W}} C'_2.

Proof. Given a graph GG, apply Lemma 4.4 to compute two orientations D0D_0 and D1:=D0opD_1 := D_0^{\mathrm{op}} of GG such that at least one of them admits a one-way directed Eulerian path. By the proof of Lemma 4.4, Di∉dom⁡(DEP⁡)D_i \notin\operatorname{dom}(\operatorname{DEP}) iff there is a vertex vv of finite degree such that in⁡Di(v)=out⁡Di(v)+1\operatorname{in}_{D_i}(v) = \operatorname{out}_{D_i}(v) + 1. This is a Σ20\Sigma^0_2 condition relative to the input graph (see also the proof of Theorem 3.4). Hence the non-empty set

A:={i∈{0,1}:Di∈dom⁡(DEP⁡)}A := \{i \in\{0,1\} : D_i \in\operatorname{dom}(\operatorname{DEP})\}

is uniformly Π20\Pi^0_2 relative to GG, and C2′C'_2 suffices to choose a valid orientation. ▫

As a corollary, we obtain e.g. that C3̸≤WOrientEP⁡C_3 \not\leq_{\mathrm{W}} \operatorname{OrientEP}, since C3̸≤WC2′C_3 \not\leq_{\mathrm{W}} C'_2 [6 Prop. 7.4]. We now show that OrientEP⁡≤WSort⁡2\operatorname{OrientEP} \leq_{\mathrm{W}} \operatorname{Sort}_2. The following observation is a simple consequence of [12 Lem. 7] (see also [9 Thm. 8.4.2]).

Lemma 4.6. Let G∈dom⁡(EP⁡)G \in\operatorname{dom}(\operatorname{EP}). If GG has no odd-degree vertex then it admits an edge-decomposition into finite cycles.

Proof. By [9 Thm. 8.4.2], it is enough to show that GG has no finite odd cut, i.e. there is no set X⊆VX \subseteq V such that the set FF of edges with exactly one endpoint in XX is finite and ∣F∣|F| is odd. Fix XX and FF as mentioned, and suppose that FF is finite. Since GG is connected, removing FF leaves only finitely many connected components, and exactly one of them is infinite (Theorem 2.1). Hence one side of the cut, say XX, is finite. Every vertex in XX has finite even degree, hence, letting EinE_{\mathrm{in}} be the set of edges between two vertices in XX, we have ∑v∈Xdeg⁡G(v)=2∣Ein∣+∣F∣\sum_{v \in X} \deg_G(v) = 2|E_{\mathrm{in}}| + |F|. Therefore ∣F∣|F| is even, as required. ▫

The proof of Lemma 4.4 can be adjusted to show that, if we are given both a graph G∈dom⁡(EP⁡)G \in\operatorname{dom}(\operatorname{EP}) and a vertex v0v_0 such that GG admits a one-way Eulerian path starting from v0v_0, then we can computably choose which one between DD and DopD^{\mathrm{op}} admits a directed Eulerian path. However, we will prove a more general lemma that will simplify the proof of OrientEP ≤W\leq_{\mathrm{W}} Sort2_2.

We say that a function φ ⁣:N→N∪{−1}\varphi\colon\mathbb{N} \to\mathbb{N} \cup\{-1\} is an enumerating function for a set A⊆NA \subseteq\mathbb{N} if ran⁡(φ)∖{−1}=A\operatorname{ran}(\varphi) \setminus\{-1\} = A. In other words, checking if n∈An \in A is a c.e. condition relative to φ\varphi.

Lemma 4.7. There is a computable procedure that, given a graph G=(V,E)∈dom⁡(EP)G = (V,E) \in\operatorname{dom}(\mathrm{EP}) and an enumerating function φ\varphi for {v∈V:deg⁡G(v) is odd}\{v \in V : \deg_G(v) \text{ is odd}\}, computes D∈OrientEP⁡(G)D \in\operatorname{OrientEP}(G).

We first explain the strategy behind the construction. By Lemma 4.6, every graph G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}) with no odd-degree vertex admits an edge-decomposition into finite cycles. A closer inspection of the proof readily reveals that the decomposition is effective. However, if there is an odd-degree vertex, a graph G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}) with an odd-degree vertex can only be edge-decomposed into T∪⋃nCnT \cup\bigcup_n C_n, where each CnC_n is a finite cycle and TT is a finite or one-way infinite trail. In this case, we use φ\varphi to decide the orientation of TT so that the resulting directed graph is in dom⁡(DEP)\operatorname{dom}(\mathrm{DEP}).

Proof. Let (es)s∈N(e_s)_{s\in\mathbb{N}} be an enumeration of EE. At each stage ss, we maintain a finite directed trail τs\tau_s, starting with τ0:=()\tau_0 := (). If ese_s is already oriented by stage ss, we just define τs+1:=τs\tau_{s+1} := \tau_s and go to the next stage. Let HsH_s be the subgraph obtained from GG by removing the oriented edges and isolated vertices. We search in parallel for one of the following:

  1. a finite cycle CC in HsH_s containing ese_s;

  1. a stage t≥st \geq s such that φ\varphi has enumerated a vertex v0v_0 by stage tt. If such tt is found, we search for a finite trail ρ\rho starting at v0v_0 and containing ese_s such that ρ\rho extends τs\tau_s and E(ρ)∖E(τs)⊆E(Hs)E(\rho) \setminus E(\tau_s) \subseteq E(H_s).

In case (1), we orient CC cyclically and go to the next stage with τs+1:=τs\tau_{s+1} := \tau_s. In case (2), we orient ρ\rho pointing away from v0v_0 and go to the next stage with τs+1:=ρ\tau_{s+1} := \rho.

We now show that the search always succeeds. If GG has no odd-degree vertex, then case (2) never occurs, and the claim follows by Lemma 4.6. Assume instead that, at stage ss, we find t≥st \geq s such that v0v_0 is enumerated by φ\varphi by stage tt. Let wsw_s be the final vertex of τs\tau_s, taking ws:=v0w_s := v_0 if τs\tau_s is empty. Observe that every finite-degree vertex of HsH_s different from wsw_s has even degree, while deg⁡Hs(ws)\deg_{H_s}(w_s) is odd if deg⁡G(ws)<∞\deg_G(w_s) < \infty. Indeed, removing cycles preserves degree parity, and removing a trail from v0v_0 to wsw_s changes parity only at its endpoints when these are distinct. If the endpoints coincide, or the trail is empty, the degree parity at v0v_0 is unchanged.

Hence the connected component KK of HsH_s containing wsw_s is infinite: if deg⁡G(ws)=∞\deg_G(w_s) = \infty, this is immediate. Otherwise, a finite KK would have exactly one odd-degree vertex, which is impossible. By Theorem 2.1, KK is the unique infinite component of HsH_s. If ese_s belongs to KK, there is a finite trail in HsH_s starting at wsw_s and containing ese_s. Appending this trail to τs\tau_s gives a ρ\rho satisfying (2). Otherwise, the component containing ese_s is finite with all degrees even, so ese_s belongs to a finite cycle and (1) applies. Thus the search succeeds in both cases.

This shows that every edge is eventually oriented. We now prove that the resulting directed graph DD admits a one-way directed Eulerian path by showing that it satisfies the hypotheses of Theorem 2.2. Clearly the underlying undirected graph of DD has an Eulerian path, and the same argument used in the proof of Lemma 4.4 shows that DD is weakly unbiased. If GG has no odd-degree vertex, the construction gives an edge-decomposition into finite directed cycles. In this case, every vertex vv satisfies in⁡D(v)=out⁡D(v)\operatorname{in}_D(v) = \operatorname{out}_D(v). Otherwise, let v0v_0 be the unique odd-degree vertex of GG. The construction gives an edge-decomposition into finite directed cycles and a finite or right-infinite directed trail TT starting at v0v_0. Observe that every directed trail contributes equally to the in-degree and out-degree of each vertex, except for its endpoint(s). If TT is right-infinite, this implies that the only unbalanced vertex is v0v_0 (for which in⁡D(v0)+1=out⁡D(v0)\operatorname{in}_D(v_0) + 1 = \operatorname{out}_D(v_0)). If TT is finite, we notice that its final vertex ww must have infinite degree. Indeed, suppose that deg⁡G(w)<∞\deg_G(w) < \infty. If w≠v0w \ne v_0, then TT contributes an odd number of edges incident to ww, while every closed trail contributes an even number. Hence deg⁡G(w)\deg_G(w) is odd, against the fact that v0v_0 is the only possible odd-degree vertex of GG. If w=v0w=v_0 then TT is closed (possibly trivial), hence deg⁡G(v0)\deg_G(v_0) is even, against the fact that deg⁡G(v0)\deg_G(v_0) is odd. Thus the degree condition holds, completing the proof.

We can notice that the construction in the previous Lemma can be adapted to show that, given G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}) and a vertex v0∈V(G)v_0 \in V(G) such that GG has an Eulerian path starting from v0v_0, we can uniformly compute a solution for OrientEP(G)\mathrm{OrientEP}(G). Indeed, the same proof applies whether v0v_0 has odd or infinite degree.

Theorem 4.8. OrientEP≤WSort2\mathrm{OrientEP} \leq_{\mathrm{W}} \mathrm{Sort}_2.

Proof. By Lemma 4.7, it is enough to show that, given G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}), we can use Sort2\mathrm{Sort}_2 to compute an enumerating function for {v∈V:deg⁡G(v) is odd}\{v \in V : \deg_G(v)\text{ is odd}\}. Let XX be the set of pairs (v,σ)∈V×N<N(v,\sigma) \in V \times\mathbb{N}^{<\mathbb{N}} such that ∣σ∣|\sigma| is odd and σ\sigma lists exactly the neighbors of vv, without repetitions. This set is uniformly Π10\Pi^0_1 relative to GG. Fix an enumeration of V×N<NV \times\mathbb{N}^{<\mathbb{N}} and define g(s)g(s) as the least pair that is not enumerated outside of XX by stage ss. We define the input pp for Sort2\mathrm{Sort}_2 as

p(s):={0if g(s+1)≠g(s),1otherwise.p(s) := \begin{cases} 0 & \text{if } g(s+1) \ne g(s),\\ 1 & \text{otherwise.} \end{cases}

Observe that if GG has an odd-degree vertex, then gg eventually stabilizes at a pair (v,σ)(v,\sigma) such that vv has odd degree and σ\sigma is a list of the neighbors of vv. Otherwise, every guess is eventually refuted, and g(s)→∞g(s) \to\infty. In particular, gg changes its value finitely many times iff GG has an odd-degree vertex.

Let q:=Sort2(p)q := \mathrm{Sort}_2(p). Observe that if GG has no odd-degree vertex, then pp contains infinitely many zeroes and q=0ωq=0^\omega. Otherwise, q=0k1ωq=0^k1^\omega, where kk is the total number of changes of gg.

In particular, given qq, we can compute an enumerating function φ\varphi as follows: we output −1-1 as long as qq contains zeroes. Once the first 11 in qq is found, using kk we can compute the final value of gg, and hence the unique odd-degree vertex of GG.

Theorem 4.5 and Theorem 4.8 immediately yield OrientEP≤WC2′⊓Sort2\mathrm{OrientEP} \leq_{\mathrm{W}} C'_2 \sqcap\mathrm{Sort}_2. We will now show that the reduction is strict. For the sake of readability, we first isolate the following lemma.

Definition 4.9. Given a directed graph FF, we can uniformly compute an enumeration (CiF)i(C_i^F)_i of all finite directed cycles in FF. For each finite σ∈N<N\sigma\in\mathbb{N}^{<\mathbb{N}}, we define ρ(σ,F)\rho(\sigma,F) recursively as follows: ρ((),F):=F\rho((),F):=F and ρ((i),F)\rho((i),F) is the directed graph obtained by reversing the orientation of the ii-th cycle CiFC_i^F in FF, and ρ(σ⌢(i),F):=ρ((i),ρ(σ,F))\rho(\sigma^\frown(i),F):=\rho((i),\rho(\sigma,F)).

Lemma 4.10. For any G∈dom⁡(EP)G \in\operatorname{dom}(\mathrm{EP}), any n∈Nn \in\mathbb{N} and any two D,H∈OrientEP(G)D,H \in\mathrm{OrientEP}(G), there is σ∈N<N\sigma\in\mathbb{N}^{<\mathbb{N}} such that Dσ:=ρ(σ,D)D_\sigma:=\rho(\sigma,D) is defined and agrees with HH on the orientation of the first nn edges of GG.

Proof. Fix G,D,HG,D,H as in the hypotheses. Observe that, for every σ∈N<N\sigma\in\mathbb{N}^{<\mathbb{N}} for which DσD_\sigma is defined, DσD_\sigma is a valid solution for OrientEP(G)\mathrm{OrientEP}(G), as reversing the orientation of a cycle does not affect the existence of a one-way directed Eulerian path. We recursively define a string σ\sigma as follows: we start with σ0:=()\sigma_0:=(). At each stage, we have a set As⊆E(Ds)A_s \subseteq E(D_s) of all the edges in DsD_s with index ≤n\leq n on which HH and DsD_s agree. Let e=u→v∈E(Ds)e=u\to v\in E(D_s) be the first edge with index ≤n\leq n on which HH and DsD_s disagree (if no such ee exists we are done).

Consider the set

X:={w∈V(G):there is a directed path from v to w in Ds−As}.X:=\{w\in V(G):\text{there is a directed path from }v\text{ to }w\text{ in }D_s-A_s\}.

If v∈Xv\in X then there is a cycle CiC_i of DsD_s proving the claim. We define σs+1:=σs⌢(i)\sigma_{s+1}:=\sigma_s^\frown(i) and go to the next stage. We show that v∉Xv\notin X leads to a contradiction. Indeed, for a directed graph FF and X⊆V(F)X\subseteq V(F), let

δout(F,X):={(x,y)∈E(F):x∈X and y∉X}\delta_{\mathrm{out}}(F,X):=\{(x,y)\in E(F):x\in X\text{ and }y\notin X\}
δin(F,X):={(y,x)∈E(F):x∈X and y∉X}.\delta_{\mathrm{in}}(F,X):=\{(y,x)\in E(F):x\in X\text{ and }y\notin X\}.

Clearly, δout(Ds,X)⊆As\delta_{\mathrm{out}}(D_s,X) \subseteq A_s hence, by definition of AsA_s, it is finite. Since DsD_s is weakly unbiased, this implies also that δin(Ds,X)\delta_{\mathrm{in}}(D_s,X) is finite. Since δ(Ds,X):=δin(Ds,X)∪δout(Ds,X)\delta(D_s,X) := \delta_{\mathrm{in}}(D_s,X) \cup\delta_{\mathrm{out}}(D_s,X) is finite, Theorem 2.1 implies that G−δ(Ds,X)G - \delta(D_s,X) (i.e. deleting the undirected edges in δ(Ds,X)\delta(D_s,X) from GG) has exactly one infinite component.

Let S:=XS := X if XX does not contain the infinite connected component of G−δ(Ds,X)G - \delta(D_s,X), and S:=V(G)∖XS := V(G) \setminus X otherwise. Since δ(Ds,X)=δ(Ds,S)\delta(D_s,X) = \delta(D_s,S), it follows that there are finitely many edges with an endpoint in SS. In particular, every one-way directed Eulerian path eventually leaves SS permanently. Since both DsD_s and HH are in dom⁡(DEP⁡)\operatorname{dom}(\operatorname{DEP}), we have that for F∈{Ds,H}F \in\{D_s,H\},

∣δout(F,S)∣−∣δin(F,S)∣={1if S contains an odd-degree vertex of G,0otherwise.|\delta_{\mathrm{out}}(F,S)| - |\delta_{\mathrm{in}}(F,S)| = \begin{cases} 1 & \text{if } S \text{ contains an odd-degree vertex of } G,\\ 0 & \text{otherwise.} \end{cases}

This can be proved using e.g. [13 Lem. 4]. This, together with ∣δ(Ds,S)∣=∣δ(H,S)∣|\delta(D_s,S)| = |\delta(H,S)| (which follows from the fact that SS has the same boundary in GG), implies that ∣δout(H,S)∣=∣δout(Ds,S)∣|\delta_{\mathrm{out}}(H,S)| = |\delta_{\mathrm{out}}(D_s,S)| and ∣δin(H,S)∣=∣δin(Ds,S)∣|\delta_{\mathrm{in}}(H,S)| = |\delta_{\mathrm{in}}(D_s,S)|. This, in turn, implies that ∣δout(H,X)∣=∣δout(Ds,X)∣|\delta_{\mathrm{out}}(H,X)| = |\delta_{\mathrm{out}}(D_s,X)|.

Since δout(Ds,X)⊆As\delta_{\mathrm{out}}(D_s,X) \subseteq A_s, it follows by definition of AsA_s that δout(Ds,X)⊆δout(H,X)\delta_{\mathrm{out}}(D_s,X) \subseteq\delta_{\mathrm{out}}(H,X). However, by construction, HH and DsD_s disagree on the direction of the edge ee, hence ∣δout(H,X)∣≥∣δout(Ds,X)∣+1|\delta_{\mathrm{out}}(H,X)| \geq|\delta_{\mathrm{out}}(D_s,X)|+1, which is a contradiction. □

Theorem 4.11. OrientEP⁡<WC2′⊓Sort⁡2\operatorname{OrientEP} <_{\mathrm{W}} C'_2 \sqcap\operatorname{Sort}_2.

Proof. The reduction follows from OrientEP⁡≤WC2′\operatorname{OrientEP} \leq_{\mathrm{W}} C'_2 (Theorem 4.5), OrientEP⁡≤WSort⁡2\operatorname{OrientEP} \leq_{\mathrm{W}} \operatorname{Sort}_2 (Theorem 4.8), as ⊓\sqcap is the meet in the Weihrauch lattice.

For the separation, suppose towards a contradiction that C2′⊓Sort⁡2≤WOrientEP⁡C'_2 \sqcap\operatorname{Sort}_2 \leq_{\mathrm{W}} \operatorname{OrientEP} via Φ,Ψ\Phi,\Psi. Recall that a solution for C2′⊓Sort⁡2(p,q)C'_2 \sqcap\operatorname{Sort}_2(p,q) is of the form b⌢yb^\frown y where b∈{0,1}b \in\{0,1\} determines whether y∈C2′(p)y \in C'_2(p) or y=Sort⁡2(q)y = \operatorname{Sort}_2(q). It is convenient to use C2′≡WRT⁡21C'_2 \equiv_{\mathrm{W}} \operatorname{RT}^{1}_{2} and therefore think of an instance of C2′C'_2 as a binary sequence p∈2Np \in2^{\mathbb{N}}, and a C2′C'_2 solution for pp is a number <2<2 that appears infinitely often in pp.

For every instance (p,q)(p,q) of C2′⊓Sort⁡2C'_2 \sqcap\operatorname{Sort}_2, we write Gp,qG_{p,q} for the graph defined by Φ(p,q)\Phi(p,q) and D0p,q,D1p,q:=(D0p,q)opD^{p,q}_0,D^{p,q}_1 := (D^{p,q}_0)^{\mathrm{op}} for the two orientations of Gp,qG_{p,q} computably obtained by Lemma 4.4. Consider the two computations Ψi(p,q):=Ψ(p,q,Dip,q)\Psi_i(p,q) := \Psi(p,q,D^{p,q}_i) for i<2i<2. By Lemma 4.4, at least one of the two computations produces a valid solution for C2′⊓Sort⁡2(p,q)C'_2 \sqcap\operatorname{Sort}_2(p,q).

We first claim that if, for every input (p,q)(p,q), every valid canonical orientation Dip,qD^{p,q}_i yields a C2′C'_2 answer, then C2′≤WOrientEP⁡C'_2 \leq_{\mathrm{W}} \operatorname{OrientEP}. This would contradict Theorem 4.8, as Sort⁡2≤Wlim⁡\operatorname{Sort}_2 \leq_{\mathrm{W}} \lim [14 Prop. 24] but C2′̸≤Wlim⁡C'_2 \not\leq_{\mathrm{W}} \lim [5 Thm. 11.7.54].

To prove the claim, assume that, for every input (p,q)(p,q) and i<2i<2, if Dip,q∈OrientEP⁡(Φ(p,q))D^{p,q}_i \in\operatorname{OrientEP}(\Phi(p,q)) then Ψi(p,q)(0)=0\Psi_i(p,q)(0)=0. Given an instance pp of C2′C'_2, produce the graph G:=Φ(p,1ω)G := \Phi(p,1^\omega) and let D∈OrientEP⁡(G)D \in\operatorname{OrientEP}(G). In parallel for every σ∈N<N\sigma\in\mathbb{N}^{<\mathbb{N}} such that Dσ:=ρ(σ,D)D_\sigma:= \rho(\sigma,D) is defined (see Definition 4.9), we run the computations Ψ(p,1ω,Dσ)\Psi(p,1^\omega,D_\sigma) until we find some σ\sigma such that Ψ(p,1ω,Dσ)(0)≠0\Psi(p,1^\omega,D_\sigma)(0) \neq0. Notice that the search is guaranteed to terminate by Lemma 4.10, because at least one canonical orientation Dip,1ωD^{p,1^\omega}_i is valid and, by assumption, its backward computation returns a C2′C'_2-answer. Besides, every enumerated DσD_\sigma is a valid solution for OrientEP⁡(Φ(p,1ω))\operatorname{OrientEP}(\Phi(p,1^\omega)), hence this establishes C2′≤WOrientEP⁡C'_2 \leq_{\mathrm{W}} \operatorname{OrientEP}.

This shows that we can choose an input (p,q)(p,q) and i<2i<2 such that Ψi(p,q)(0)≠1\Psi_i(p,q)(0) \neq1. We now diagonalize against Φ,Ψ\Phi,\Psi by showing that there is an input (p∗,q∗)(p_*,q_*) for C2′⊓Sort⁡2C'_2 \sqcap\operatorname{Sort}_2 on which the reduction fails to produce a valid answer. Let n0n_0 be sufficiently large so that Ψi(p[n0],q[n0])(0)≠1\Psi_i(p[n_0],q[n_0])(0) \neq1.

We first show that there are two strings σ⊏p\sigma\sqsubset p, τ⊏q[n0]1ω\tau\sqsubset q[n_0]1^\omega such that, for some kk, 10k1⊑Ψi(σ,τ)10^k1 \sqsubseteq\Psi_i(\sigma,\tau). Indeed, consider both computations Ψj(p,q[n0]1ω)\Psi_j(p,q[n_0]1^\omega) for j<2j<2. If there are no σ,τ\sigma,\tau as above, then Ψi(p,q[n0]1ω)∉C2′⊓Sort⁡2(p,q[n0]1ω)\Psi_i(p,q[n_0]1^\omega) \notin C'_2 \sqcap\operatorname{Sort}_2(p,q[n_0]1^\omega). This implies that Ψ1−i(p,q[n0]1ω)\Psi_{1-i}(p,q[n_0]1^\omega) is the correct one instead. By continuity, there are sufficiently long prefixes σ⊏p\sigma\sqsubset p and τ⊏q[n0]1ω\tau\sqsubset q[n_0]1^\omega on which Ψ1−i(σ,τ)\Psi_{1-i}(\sigma,\tau) produces either 0b0b for some b<2b<2 or 10k110^k1 for some k∈Nk \in\mathbb{N}. In the first case, set p∗:=σ⌢(1−b)ωp_* := \sigma^\frown(1-b)^\omega and τ∗:=τ\tau_* := \tau, otherwise set p∗:=pp_* := p and τ∗:=τ⌢0k1\tau_* := \tau^\frown0^k1. In both cases, we are forcing Ψ1−i\Psi_{1-i} to produce the wrong C2′⊓Sort⁡2C'_2 \sqcap\operatorname{Sort}_2 answer on every input of the form (p∗,q∗)(p_*,q_*) where q∗⊒τ∗q_* \sqsupseteq\tau_*. Hence, letting hh be the number of zeroes in τ∗\tau_\ast, there is m∈Nm \in\mathbb{N} such that 10h1⊑Ψi(p∗,τ∗⌢1m)10^{h}1 \sqsubseteq\Psi_i(p_\ast,\tau_\ast\mathbin{{}^\smallfrown}1^m).

By continuity, this implies that the pair Φ,Ψ\Phi,\Psi fails to produce the correct C2′⊓Sort⁡2C'_2 \sqcap\operatorname{Sort}_2 answer for (p∗,q∗:=τ∗⌢1m0ω)(p_\ast,q_\ast:= \tau_\ast\mathbin{{}^\smallfrown}1^m0^\omega), against the definition of Weihrauch reducibility.

To conclude the proof, fix σ,τ∈2<N\sigma,\tau\in2^{<\mathbb{N}} and k∈Nk \in\mathbb{N} as above. In this case, letting q1:=τ⌢0ωq_1 := \tau\mathbin{{}^\smallfrown}0^\omega, we obtain that for every p⊒σp \sqsupseteq\sigma, Ψi(p,q1)\Psi_i(p,q_1) does not produce a valid C2′⊓Sort⁡2C'_2 \sqcap\operatorname{Sort}_2 answer.

We distinguish two cases:

  • if, for some jj and some sufficiently large n1n_1, (0,j)⊑Ψ1−i(p[n1],q1[n1])(0,j) \sqsubseteq\Psi_{1-i}(p[n_1],q_1[n_1]), then, we let p∗:=p[n1]⌢(1−j)ωp_\ast:= p[n_1]\mathbin{{}^\smallfrown}(1-j)^\omega and q∗:=q1q_\ast:= q_1.

  • if, for some sufficiently large n1n_1, Ψ1−i(p[n1],q1[n1])(0)=1\Psi_{1-i}(p[n_1],q_1[n_1])(0)=1, then, by continuity, there are t∈Nt \in\mathbb{N} and m∈Nm \in\mathbb{N} such that 10m1⊑Ψ1−i(p,q1[n1]⌢1t)10^m1 \sqsubseteq\Psi_{1-i}(p,q_1[n_1]\mathbin{{}^\smallfrown}1^t) (such mm must exist because q1[n1]⌢1ωq_1[n_1]\mathbin{{}^\smallfrown}1^\omega contains finitely many zeroes). We define p∗:=pp_\ast:= p and q∗:=q1[n1]⌢1t0ωq_\ast:= q_1[n_1]\mathbin{{}^\smallfrown}1^t0^\omega.

In both cases, we obtain that neither Ψ0(p∗,q∗)\Psi_0(p_\ast,q_\ast) nor Ψ1(p∗,q∗)\Psi_1(p_\ast,q_\ast) are valid solutions, as required. □

Two-way Eulerian paths

We now turn our attention to the case of two-way Eulerian paths.

Definition 5.1. Let EP⁡2\operatorname{EP}_2 (resp. DEP⁡2\operatorname{DEP}_2) be the problem that takes as input an infinite countable undirected (resp. directed) graph that has a two-way Eulerian path, and outputs a sequence (xn)n∈Z(x_n)_{n\in\mathbb{Z}} of vertices forming such a path.

Recall that, by Theorem 3.4, EP⁡≡WDEP⁡≡WCN′×lim⁡\operatorname{EP}\equiv_{\mathrm{W}}\operatorname{DEP}\equiv_{\mathrm{W}} C'_{\mathbb{N}}\times\lim. Intuitively, the first half (CN′C'_{\mathbb{N}}) comes from the difficulty of “starting the path”, while the second half (lim⁡\lim) is the complexity of finding “the tail of the path”. Obviously, there is no “start” in a two-way Eulerian path, and indeed we can show that EP⁡2≡WDEP⁡2≡Wlim⁡\operatorname{EP}_2\equiv_{\mathrm{W}}\operatorname{DEP}_2\equiv_{\mathrm{W}}\lim. For the sake of readability, we split the proof in two results, one for the undirected and one for the directed case.

Theorem 5.2. EP⁡2≡Wlim⁡\operatorname{EP}_2\equiv_{\mathrm{W}}\lim.

Proof. The reduction lim⁡≤WEP⁡2\lim\leq_{\mathrm{W}}\operatorname{EP}_2 can be proved with a simple modification of the graph used in the proof of lim⁡≤WEP⁡start\lim\leq_{\mathrm{W}}\operatorname{EP}_{\mathrm{start}} (Theorem 3.2), where the only difference is that the vertices {bn:n∈N}\{b_n:n\in\mathbb{N}\} are now arranged so as to form a two-way line …−b3−b1−b0−b2−b4−…\ldots-b_3-b_1-b_0-b_2-b_4-\ldots.

Let us now show that EP⁡2≤Wlim⁡\operatorname{EP}_2\leq_{\mathrm{W}}\lim. Let G=(V,E)G=(V,E) be an instance of EP⁡2\operatorname{EP}_2. By [7 Prop. 4.13], a finite trail τ\tau with initial vertex uu and final vertex vv is extendible to a two-way Eulerian path iff

  1. there are distinct edges e,f∈E∖E(τ)e,f\in E\setminus E(\tau) incident to uu and vv, respectively;

  2. every connected component of G−E(τ)G-E(\tau) contains uu or vv.

We show that these conditions are uniformly Δ20\Delta^0_2 relative to GG and τ\tau. The first condition is Σ10\Sigma^0_1 relative to GG and τ\tau, since we can search for two distinct unused edges incident to the endpoints. The second condition is equivalent to requiring that, for every w∈ran⁡(τ)w\in\operatorname{ran}(\tau), one of the following holds:

(I) E(τ)E(\tau) contains all the edges incident to ww, or

(II) there is a finite trail from ww to uu or vv in G−E(τ)G-E(\tau).

To see that, let H:=G−E(τ)H:=G-E(\tau). Assume first that (2) holds and let w∈ran⁡(τ)w\in\operatorname{ran}(\tau). If ww has an incident edge that is not contained in τ\tau, then w∈V(H)w\in V(H), hence (2) implies that there is a finite trail from ww to either uu or vv. Conversely, fix a connected component CC of HH. Since GG is connected, CC contains some vertex ww of ran⁡(τ)\operatorname{ran}(\tau): take any path from CC to ran⁡(τ)\operatorname{ran}(\tau). For this ww, (I) fails (as otherwise ww would not be in V(H)V(H)), hence (II) holds, and therefore CC contains either uu or vv.

Observe that the conditions (I) and (II) are, respectively, Π10\Pi^0_1 and Σ10\Sigma^0_1 relative to GG and τ\tau. This implies that, using lim⁡≡WLPOd\lim\equiv_{\mathrm{W}} \mathrm{LPO}^{\mathrm{d}}, we can check which finite trail τ\tau is extendible to a two-way Eulerian path.

To conclude the proof, we observe that such a path can be computed (uniformly) by greedy search while ensuring that all the edges are visited: fix an enumeration (en)n∈N(e_n)_{n\in\mathbb{N}} of EE. Let e0:={u,v}e_0 := \{u,v\}. We start with τ0(0):=u\tau_0(0) := u and τ0(1):=v\tau_0(1) := v. At stage s+1s+1, we have defined a finite trail τs\tau_s with endpoints usu_s and vsv_s. We search for a finite trail τs+1\tau_{s+1} extending τs\tau_s such that

  • τs+1\tau_{s+1} is extendible to an infinite two-way Eulerian path.

  • es+1∈E(τs+1)e_{s+1} \in E(\tau_{s+1})

  • τs+1\tau_{s+1} extends τs\tau_s by adding at least one additional edge at each end.

By the inductive hypothesis, such a trail exists, and, in the limit, this construction yields a solution for EP2(G)\mathrm{EP}_2(G).

To characterize the degree of DEP2\mathrm{DEP}_2, we first prove an auxiliary result.

Lemma 5.3. Let D=(V,E)D=(V,E) be a directed graph admitting a two-way directed Eulerian path. Let τ\tau be a finite directed trail and let u:=τ(0)u := \tau(0) and v:=τ(∣τ∣−1)v := \tau(|\tau|-1). Define the graph HH as the directed graph obtained from D−E(τ)D-E(\tau) by adding a fresh vertex zz and the edges u→zu \to z and z→vz \to v.

Then τ\tau extends to a two-way Eulerian path in DD iff the underlying undirected graph of HH is connected.

Proof. Suppose first that τ\tau extends to a two-way directed Eulerian path in DD. Replacing the occurrence of τ\tau in this path by u→z→vu \to z \to v gives a two-way directed Eulerian path in HH. In particular, the underlying undirected graph of HH is connected.

Conversely, suppose that the underlying undirected graph of HH is connected. We show that HH admits a two-way directed Eulerian path. This implies that τ\tau extends to a two-way Eulerian path in DD: indeed, every two-way Eulerian path in HH must traverse the edges u→z→vu \to z \to v. Replacing the finite trail u→z→vu \to z \to v with τ\tau gives a two-way Eulerian path in DD extending τ\tau.

Let X=(xn)n∈ZX=(x_n)_{n\in\mathbb{Z}} be a two-way Eulerian path in DD and let σ\sigma be a finite subtrail of XX containing every edge of τ\tau. Define a:=σ(0)a := \sigma(0) and b:=σ(∣σ∣−1)b := \sigma(|\sigma|-1). Without loss of generality, we can assume a≠ba \ne b (extending σ\sigma if necessary). Consider the finite directed subgraph FF of HH such that

E(F)=(E(σ)∖E(τ))∪{(u,z),(z,v)}.E(F)=(E(\sigma)\setminus E(\tau))\cup\{(u,z),(z,v)\}.

Observe that, since the two trails τ\tau and u→z→vu \to z \to v have the same endpoints, for every vertex x∈V(F)∖{a,b}x \in V(F)\setminus\{a,b\}

out⁡F(x)−in⁡F(x)=0.\operatorname{out}_F(x)-\operatorname{in}_F(x)=0.

Besides, out⁡F(a)=in⁡F(a)+1\operatorname{out}_F(a)=\operatorname{in}_F(a)+1 and in⁡F(b)=out⁡F(b)+1\operatorname{in}_F(b)=\operatorname{out}_F(b)+1. This implies that FF can be decomposed into finitely many edge-disjoint cycles C0,…,Ck−1C_0,\ldots,C_{k-1} and a finite open directed trail η\eta from aa to bb. This can be proved e.g. applying [2 Ex. 4.8] to the graph obtained by adding a fresh auxiliary vertex cc and the edges b→cb \to c and c→ac \to a to FF.

Let Y0=(yn)n∈ZY_0=(y_n)_{n\in\mathbb{Z}} be the two-way directed trail obtained by replacing σ\sigma with η\eta in XX. We extend Y0Y_0 by attaching each cycle CiC_i in stages as follows: at each stage s<ks<k, we have a list of unused cycles. Since HH is connected there is i<ki<k such that, for some unused cycle Ci=(wni)n<∣Ci∣C_i=(w_n^i)_{n<|C_i|} (with the assumption that w0i=w∣Ci∣−1iw_0^i=w_{|C_i|-1}^i), CiC_i has some vertex in common with YsY_s. Choose nn such that ynsy_n^s belongs to CiC_i. We define Ys+1Y_{s+1} by visiting CiC_i between ynsy_n^s and yn+1sy_{n+1}^s. More formally, modulo reindexing CiC_i, we can assume w0i=ynsw_0^i = y_n^s. We define

yms+1:={ymsif m≤n,wm−niif n<m<n+∣Ci∣,ym−∣Ci∣+1sif n+∣Ci∣≤m.y_m^{s+1}:= \begin{cases} y_m^s & \text{if }m \le n,\\ w_{m-n}^i & \text{if }n < m < n+|C_i|,\\ y_{m-|C_i|+1}^s & \text{if }n+|C_i| \le m. \end{cases}

We then label CiC_i as used and go to the next stage. Each stage is possible because HH is connected, and the procedure terminates after kk stages. The trail YkY_k is a two-way directed Eulerian path through HH, which concludes the proof.

Theorem 5.4. DEP2≡Wlim⁡\mathrm{DEP}_2 \equiv_{\mathrm{W}} \lim.

Proof. The reduction lim⁡≤WDEP2\lim\le_{\mathrm{W}} \mathrm{DEP}_2 is obtained by a straightforward modification of the construction in Theorem 3.2 (see also the proof of Theorem 5.2): arrange the vertices {bn:n∈N}\{b_n:n\in\mathbb{N}\} in a two-way line …→b3→b1→b0→b2→b4→…\ldots\to b_3 \to b_1 \to b_0 \to b_2 \to b_4 \to\ldots.

For the converse reduction, let D=(V,E)D=(V,E) be an instance of DEP2\mathrm{DEP}_2. For each nonempty finite directed trail τ\tau, let HτH_\tau be the graph obtained by replacing E(τ)E(\tau) with u→z→vu\to z\to v as in Lemma 5.3. We show that connectedness of the underlying undirected graph of HτH_\tau is uniformly Δ20\Delta_2^0 relative to DD and τ\tau.

Observe that HτH_\tau is connected iff, for every w∈ran⁡(τ)w\in\operatorname{ran}(\tau), at least one of the following holds:

  1. every edge of DD incident to ww belongs to E(τ)E(\tau);

  2. there is a finite undirected path in HτH_\tau from ww to zz.

For the forward implication, if (1) fails, then ww is a vertex of HτH_\tau, so connectedness gives (2). Conversely, let GG be the underlying undirected graph of D−E(τ)D-E(\tau). Since DD is connected, every connected component of D−E(τ)D-E(\tau) contains a vertex w∈ran⁡(τ)w\in\operatorname{ran}(\tau). By construction, every such vertex ww has an edge that does not belong to E(τ)E(\tau). In particular, by (2), ww is connected to zz in HτH_\tau. Since, clearly, uu and vv are connected to zz, this shows that HτH_\tau is connected.

Conditions (1) and (2) are respectively Π10\Pi_1^0 and Σ10\Sigma_1^0 relative to DD and τ\tau, and hence, since ran⁡(τ)\operatorname{ran}(\tau) is finite, checking if HτH_\tau is connected is uniformly Δ20\Delta_2^0 in DD and τ\tau. We can therefore use lim⁡≡WLPOd\lim\equiv_{\mathrm{W}}\mathrm{LPO}^{\mathrm{d}} to check which τ\tau extend to a two-way Eulerian path.

To complete the proof, fix an enumeration (es)s∈N(e_s)_{s\in\mathbb{N}} of EE. At each stage, we greedily search for an extension τs+1\tau_{s+1} of the finite trail τs\tau_s built so far such that

  • τs+1\tau_{s+1} is extendible,

  • τs+1\tau_{s+1} contains ese_s,

  • τs+1\tau_{s+1} extends τs\tau_s by adding at least one edge at each end.

We start with τ0:=e0\tau_0:=e_0. Since D∈dom⁡(DEP2)D\in\operatorname{dom}(\mathrm{DEP}_2) the search is guaranteed to succeed at each stage. In the limit, we obtain a two-way trail passing through each edge, and therefore it is a valid solution for DEP2(D)\mathrm{DEP}_2(D).

Similarly to the case of one-way Eulerian paths, we can consider the problem of orienting the edges of an undirected graph while preserving the existence of a two-way (directed or undirected) Eulerian path.

Definition 5.5. Let OrientEP2\mathrm{OrientEP}_2 be the problem that, given G=(V,E)∈dom⁡(EP2)G=(V,E)\in\operatorname{dom}(\mathrm{EP}_2), returns D=(V,A)∈dom⁡(DEP2)D=(V,A)\in\operatorname{dom}(\mathrm{DEP}_2) such that the map π:A→E:(v,w)↦{v,w}\pi:A\to E:(v,w)\mapsto\{v,w\} is a (computable) bijection.

Unlike what happens for the case of one-way Eulerian paths, finding an orientation of the edges of an undirected graph so that the resulting directed graph admits a two-way Eulerian path is computable.

Theorem 5.6. The problem OrientEP2_2 is computable.

Proof. Let G∈dom⁡(EP2)G \in\operatorname{dom}(\mathrm{EP}_2). We claim that the algorithm used in Lemma 4.4 to build the directed graph DD gives a valid solution for OrientEP2(G)\mathrm{OrientEP}_2(G). Recall that the construction builds an edge-decomposition D=R∪⋃i∈ICiD = R \cup\bigcup_{i \in I} C_i, where each CiC_i is a finite directed closed trail, I⊆NI \subseteq\mathbb{N} could be finite or infinite, and RR is a trail and could be empty, finite, one-way infinite, or two-way infinite. The construction maintains a finite directed open trail τs\tau_s at each stage, and tries to progress the edge-decomposition by searching for a finite directed trail ρ\rho that only includes edges that have not been oriented so far such that ρ\rho satisfies one of the following (ene_n is the first edge that has not been oriented by stage ss):

  1. ρ\rho includes ene_n and is a closed trail edge-disjoint from τs\tau_s;

  2. ρ\rho includes ene_n and can be either prepended or appended to τs\tau_s to form an open directed trail;

  3. ρ\rho can be appended to τs\tau_s to form a closed trail.

To show that the search always succeeds, let HH be the undirected graph of edges that have not been oriented by stage ss, and let KK be the connected component of HH containing ene_n. Let also uu and vv be the two endpoints of τs\tau_s. As in the proof of Lemma 4.4, if neither (1), (2), nor (3) is possible, then u∉Ku \notin K, v∉Kv \notin K, and KK is infinite. Observe now that both uu and vv have unused incident edges, since the construction has removed an odd number of edges incident to each of them, while their degrees in GG are even or infinite. Assume that uu and vv belong to different connected components. The connected component KuK_u of uu is infinite: if it were finite, uu would be the only odd-degree vertex in KuK_u, therefore the sum of the degrees of the vertices in KuK_u would be odd, which is impossible for a finite graph. Likewise, the connected component KvK_v of vv is infinite. Together with KK, this would give three infinite components after deleting finitely many edges from GG, contrary to Theorem 2.3. Thus u,vu,v lie in the same connected component of HH, and (3) is possible.

To conclude the proof, we need to show that DD is strongly unbiased. Fix X⊆V(G)X \subseteq V(G). Let δin(X)\delta_{\mathrm{in}}(X) (resp. δout(X)\delta_{\mathrm{out}}(X)) be the set of edges entering (resp. leaving XX). Observe that, if we define, for a directed subgraph FF,

δF→X:={(u,v)∈E(F):u∈V(F)∖X,v∈X}\delta_{F\to X} := \{(u,v) \in E(F) : u \in V(F) \setminus X, v \in X\}
δX→F:={(v,u)∈E(F):u∈V(F)∖X,v∈X},\delta_{X\to F} := \{(v,u) \in E(F) : u \in V(F) \setminus X, v \in X\},

then

∣δin(X)∣=∣δR→X∣+∑i∈I∣δCi→X∣|\delta_{\mathrm{in}}(X)| = |\delta_{R\to X}| + \sum_{i \in I} |\delta_{C_i\to X}|
∣δout(X)∣=∣δX→R∣+∑i∈I∣δX→Ci∣.|\delta_{\mathrm{out}}(X)| = |\delta_{X\to R}| + \sum_{i \in I} |\delta_{X\to C_i}|.

Since each CiC_i has equally many edges entering and leaving XX, ∑i∈I∣δCi→X∣=∑i∈I∣δX→Ci∣\sum_{i \in I} |\delta_{C_i\to X}| = \sum_{i \in I} |\delta_{X\to C_i}|. Consequently, if they are both infinite then both ∣δin(X)∣|\delta_{\mathrm{in}}(X)| and ∣δout(X)∣|\delta_{\mathrm{out}}(X)| are infinite. Assume now that they are both finite. Observe that, along a directed trail RR, the edges entering and leaving XX alternate. Therefore, either ∣δX→R∣=∣δR→X∣=∞|\delta_{X\to R}| = |\delta_{R\to X}| = \infty, and hence both ∣δin(X)∣|\delta_{\mathrm{in}}(X)| and ∣δout(X)∣|\delta_{\mathrm{out}}(X)| are infinite, or ∣∣δout(X)∣−∣δin(X)∣∣=∣∣δX→R∣−∣δR→X∣∣≤1\bigl||\delta_{\mathrm{out}}(X)| - |\delta_{\mathrm{in}}(X)|\bigr| = \bigl||\delta_{X\to R}| - |\delta_{R\to X}|\bigr| \leq1. This shows that DD is strongly unbiased.

Since GG (and hence the underlying undirected graph of DD) admits a two-way Eulerian path, by Theorem 2.4 we conclude that DD admits a two-way directed Eulerian path, and hence D∈OrientEP2(G)D \in\mathrm{OrientEP}_2(G).

Manlio Valenti

Department of Computer Science, Swansea University, Swansea, SA1 8EN, UK

Email address: [email protected]

References

  1. [1]Andrews, Uri, Lempp, Steffen, Marcone, Alberto, Miller, Joseph S., and Valenti, Manlio, A jump operator on the Weihrauch degrees, Computability 14 (2025), no. 2, 73–94, doi:10.1177/22113568241309768. MR 5000365DOI
  2. [2]Bang-Jensen, Jørgen and Gutin, Gregory, Digraphs, 2 ed., Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2009, doi:10.1007/978-1-84800-998-1, Theory, algorithms and applications. MR 2472389
  3. [3]Bean, Dwight R., Recursive Euler and Hamilton paths, Proceedings of the American Mathematical Society 55 (1976), no. 2, 385–394, doi:10.2307/2041731. MR 416888DOI
  4. [4]Brattka, Vasco, Gherardi, Guido, and Marcone, Alberto, The Bolzano-Weierstrass Theorem is the jump of Weak König’s Lemma, Annals of Pure and Applied Logic 163 (2012), no. 6, 623–655, doi:10.1016/j.apal.2011.10.006. MR 3650357
  5. [5]Brattka, Vasco, Gherardi, Guido, and Pauly, Arno, Weihrauch Complexity in Computable Analysis, Handbook of Computability and Complexity in Analysis (Brattka, Vasco and Hertling, Peter, eds.), Springer, Cham, Jul 2021, doi:10.1007/978-3-030-59234-9_11, pp. 367–417. MR 4300761DOI
  6. [6]Brattka, Vasco and Rakotoniaina, Tahina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic 82 (2017), no. 4, 1278–1316, doi:10.1017/jsl.2017.43. MR 3743611DOI
  7. [7]Carrasco-Vargas, Nicanor, Infinite Eulerian paths are computable on graphs with vertices of infinite degree, Computability 14 (2025), no. 2, 95–110, doi:10.1177/22113568251359095. MR 5000366
  8. [8]Carrasco-Vargas, Nicanor, Delle Rose, Valentino, and Rojas, Cristóbal, Paths, ends and the separation problem for infinite graphs, Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences 386 (2026), 139–155, doi:10.1016/j.dam.2026.02.004. MR 5029912
  9. [9]Diestel, Reinhard, Graph theory, 6 ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2025, doi:10.1007/978-3-662-70107-2. MR 4874150DOI
  10. [10]Gasarch, William and Hirst, Jeffry L., Reverse mathematics and recursive graph theory, Mathematical Logic Quarterly 44 (1998), no. 4, 465–473, doi:10.1002/malq.19980440405. MR 1654281DOI
  11. [12]Nash-Williams, C. St. J. A., Decomposition of graphs into closed and endless chains, Proceedings of the London Mathematical Society. Third Series 10 (1960), 221–238, doi:10.1112/plms/s3-10.1.221. MR 113810
  12. [13]———, Euler lines in infinite directed graphs, Canadian Journal of Mathematics 18 (1966), 692–714, doi:10.4153/CJM-1966-070-2. MR 200197
  13. [14]Neumann, Eike and Pauly, Arno, A topological view on algebraic computation models, Journal of Complexity 44 (2018), 1–22, doi:10.1016/j.jco.2017.08.003. MR 3724808DOI
  14. [15]Ore, Oystein, Theory of graphs, American Mathematical Society Colloquium Publications, vol. Vol. XXXVIII, American Mathematical Society, Providence, RI, 1962, doi:10.1090/coll/038. MR 150753DOI
  15. [16]Soldà, Giovanni and Valenti, Manlio, Algebraic properties of the first-order part of a problem, Annals of Pure and Applied Logic 174 (2023), no. 7, Paper No. 103270, 41, doi:10.1016/j.apal.2023.103270. MR 4583071DOI

Paper details

vlnc:W_vw7s783s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents