Embeddability of graphs and Weihrauch degrees

We study the complexity of the following computational tasks concerning a fixed countable graph [Formula: see text]: 1. Does a countable graph [Formula: see text] provided as input have a(n induced) subgraph isomorphic to [Formula: see text]? 2. Given a countable graph [Formula: see text] that has a(n induced) subgraph isomorphic to [Formula: see text], find such a subgraph. The frameworks for our investigations are 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.