Embeddability of graphs and Weihrauch degrees

arXiv2305.00935MaRDI QIDQ6509899FDOQ6509899

Abstract: 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.

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05) Other degrees and reducibilities in computability and recursion theory (03D30)

This page was built for publication: Embeddability of graphs and Weihrauch degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509899)