Embeddability of graphs and Weihrauch degrees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914642453856256 |
|---|---|
| author | Cipriani, Vittorio Pauly, Arno |
| author_facet | Cipriani, Vittorio Pauly, Arno |
| contents | We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph isomorphic to G? 2. Given a countable graph H that has a(n induced) subgraph isomorphic to G, find such a subgraph. The framework for our investigations is given by effective Wadge reducibility and by Weihrauch reducibility. Our work follows on "Reverse mathematics and Weihrauch analysis motivated by finite complexity theory" (Computability, 2021) by BeMent, Hirst and Wallace, and we answer several of their open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_00935 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Embeddability of graphs and Weihrauch degrees Cipriani, Vittorio Pauly, Arno Logic Logic in Computer Science Combinatorics 05C60, 54H05, 03D30 We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph isomorphic to G? 2. Given a countable graph H that has a(n induced) subgraph isomorphic to G, find such a subgraph. The framework for our investigations is given by effective Wadge reducibility and by Weihrauch reducibility. Our work follows on "Reverse mathematics and Weihrauch analysis motivated by finite complexity theory" (Computability, 2021) by BeMent, Hirst and Wallace, and we answer several of their open questions. |
| title | Embeddability of graphs and Weihrauch degrees |
| topic | Logic Logic in Computer Science Combinatorics 05C60, 54H05, 03D30 |
| url | https://arxiv.org/abs/2305.00935 |