On the query complexity of estimating the distance to hereditary graph properties
Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan regularity lemma and on a removal lemma for $\mathcal{F}$.
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
June 9, 2021
|
| In: |
SIAM journal on discrete mathematics
Year: 2021, Jahrgang: 35, Heft: 2, Pages: 1238-1251 |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1283951 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1137/19M1283951 Verlag, lizenzpflichtig, Volltext: https://epubs.siam.org/doi/10.1137/19M1283951 
|
| Verfasserangaben: | Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni |
| Zusammenfassung: | Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan regularity lemma and on a removal lemma for $\mathcal{F}$. |
|---|---|
| Beschreibung: | Gesehen am 19.09.2021 |
| Beschreibung: | Online Resource |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1283951 |