Can I read On the complexity of the Eulerian path problem for infinite graphs on EtoBox?

On the complexity of the Eulerian path problem for infinite graphs by Carrasco-Vargas, Nicanor; Rose, Valentino Delle; Rojas, Cristóbal is a scholarly article available to read on EtoBox.

What is On the complexity of the Eulerian path problem for infinite graphs about?

We revisit the problem of algorithmically deciding whether a given infinite connected graph has an Eulerian path, namely, a path that uses every edge exactly once. It has been recently observed that this problem is $D_3^0$-complete for graphs that have a computable description, whereas it is $\Pi_2^0$-complete for graphs that have a highly computable description, and that this same bound holds for the class of automatic graphs. A closely related problem consists of determining the number of ends of a graph, namely, the maximum number of distinct infinite connected components the graph can be separated into after removing a finite set of edges. The complexity of this problem for highly computable graphs is known to be $\Pi_2^0$-complete as well. The connection between these two problems lies in that only graphs with one or two ends can have Eulerian paths. In this paper we are interested in understanding the complexity of the infinite Eulerian path problem in the setting where the input graphs are known to have the right number of ends. We find that in this setting the problem becomes strictly easier, and that its exact difficulty varies according to whether the graphs have one or t

Author

Carrasco-Vargas, Nicanor; Rose, Valentino Delle; Rojas, Cristóbal

Published

2024

Language

EN