Paths, Ends and The Separation Problem for Infinite Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917261407682560 |
|---|---|
| author | Carrasco-Vargas, Nicanor Rose, Valentino Delle Rojas, Cristóbal |
| author_facet | Carrasco-Vargas, Nicanor Rose, Valentino Delle Rojas, Cristóbal |
| contents | We introduce and study the Separation Problem for infinite graphs, which involves determining whether a connected graph splits into at least two infinite connected components after the removal of a given finite set of edges. We prove that this problem is decidable for every highly computable graph with finitely many ends. Using this result, we demonstrate that König's Infinity Lemma is effective for such graphs. We also apply it to analyze the complexity of the Eulerian Path Problem for infinite graphs, showing that much of its complexity arises from counting ends. Indeed, the Eulerian Path Problem becomes strictly easier when restricted to graphs with a fixed number of ends. Under this restriction, we provide a complete characterization of the problem. Finally, we study the Separation Problem in a uniform setting (i.e., where the graph is also part of the input) and offer a nearly complete characterization of its complexity and its relationship to counting the number of ends. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03113 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Paths, Ends and The Separation Problem for Infinite Graphs Carrasco-Vargas, Nicanor Rose, Valentino Delle Rojas, Cristóbal Logic Combinatorics 03C57 (primary), 03D45, 05C45, 05C85, 68R10 (secondary) We introduce and study the Separation Problem for infinite graphs, which involves determining whether a connected graph splits into at least two infinite connected components after the removal of a given finite set of edges. We prove that this problem is decidable for every highly computable graph with finitely many ends. Using this result, we demonstrate that König's Infinity Lemma is effective for such graphs. We also apply it to analyze the complexity of the Eulerian Path Problem for infinite graphs, showing that much of its complexity arises from counting ends. Indeed, the Eulerian Path Problem becomes strictly easier when restricted to graphs with a fixed number of ends. Under this restriction, we provide a complete characterization of the problem. Finally, we study the Separation Problem in a uniform setting (i.e., where the graph is also part of the input) and offer a nearly complete characterization of its complexity and its relationship to counting the number of ends. |
| title | Paths, Ends and The Separation Problem for Infinite Graphs |
| topic | Logic Combinatorics 03C57 (primary), 03D45, 05C45, 05C85, 68R10 (secondary) |
| url | https://arxiv.org/abs/2409.03113 |