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}$.
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
June 9, 2021
|
| In: |
SIAM journal on discrete mathematics
Year: 2021, Volume: 35, Issue: 2, Pages: 1238-1251 |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1283951 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1137/19M1283951 Verlag, lizenzpflichtig, Volltext: https://epubs.siam.org/doi/10.1137/19M1283951 
|
| Author Notes: | Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni |
| Summary: | 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}$. |
|---|---|
| Item Description: | Gesehen am 19.09.2021 |
| Physical Description: | Online Resource |
| ISSN: | 1095-7146 |
| DOI: | 10.1137/19M1283951 |