We consider several variations of the following problem: fix a countable graph G. Is an input graph H a(n induced) subgraph of G? If yes, can we find a copy of H in G? The challenge to classify the Weihrauch degrees of such problems was put forth recently by BeMent, Hirst, and Wallace (“Reverse mathematics and Weihrauch analysis motivated by finite complexity theory”, Computability, 2021). We report some initial results here, and in particular, solve one of their open questions.
The Complexity of Finding Supergraphs
Cipriani V.;
2023-01-01
Abstract
We consider several variations of the following problem: fix a countable graph G. Is an input graph H a(n induced) subgraph of G? If yes, can we find a copy of H in G? The challenge to classify the Weihrauch degrees of such problems was put forth recently by BeMent, Hirst, and Wallace (“Reverse mathematics and Weihrauch analysis motivated by finite complexity theory”, Computability, 2021). We report some initial results here, and in particular, solve one of their open questions.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Deciding_embeddability_of_graphs_1_.pdf
non disponibili
Licenza:
Non pubblico
Dimensione
340.77 kB
Formato
Adobe PDF
|
340.77 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
