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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1770928952 | ||
| 003 | DE-627 | ||
| 005 | 20220820044503.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 210919s2021 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1137/19M1283951 |2 doi | |
| 035 | |a (DE-627)1770928952 | ||
| 035 | |a (DE-599)KXP1770928952 | ||
| 035 | |a (OCoLC)1341421333 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Hoppen, Carlos |e VerfasserIn |0 (DE-588)1241461538 |0 (DE-627)1770928944 |4 aut | |
| 245 | 1 | 0 | |a On the query complexity of estimating the distance to hereditary graph properties |c Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni |
| 264 | 1 | |c June 9, 2021 | |
| 300 | |a 14 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 19.09.2021 | ||
| 520 | |a 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}$. | ||
| 650 | 4 | |a 05C35 | |
| 650 | 4 | |a 05C85 | |
| 650 | 4 | |a 05D40 | |
| 650 | 4 | |a 68W20 | |
| 650 | 4 | |a edit distance | |
| 650 | 4 | |a Frieze;Kannan regularity | |
| 650 | 4 | |a hereditary properties | |
| 650 | 4 | |a parameter testing | |
| 650 | 4 | |a removal lemma | |
| 700 | 1 | |a Kohayakawa, Yoshiharu |e VerfasserIn |4 aut | |
| 700 | 1 | |a Lang, Richard |e VerfasserIn |0 (DE-588)122670008X |0 (DE-627)1747737372 |4 aut | |
| 700 | 1 | |a Lefmann, Hanno |e VerfasserIn |4 aut | |
| 700 | 1 | |a Stagni, Henrique |e VerfasserIn |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Society for Industrial and Applied Mathematics |t SIAM journal on discrete mathematics |d Philadelphia, Pa. : Soc., 1988 |g 35(2021), 2, Seite 1238-1251 |h Online-Ressource |w (DE-627)26688539X |w (DE-600)1468404-4 |w (DE-576)078589975 |x 1095-7146 |7 nnas |
| 773 | 1 | 8 | |g volume:35 |g year:2021 |g number:2 |g pages:1238-1251 |g extent:14 |a On the query complexity of estimating the distance to hereditary graph properties |
| 856 | 4 | 0 | |u https://doi.org/10.1137/19M1283951 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://epubs.siam.org/doi/10.1137/19M1283951 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20210919 | ||
| 993 | |a Article | ||
| 994 | |a 2021 | ||
| 998 | |g 122670008X |a Lang, Richard |m 122670008X:Lang, Richard |d 110000 |d 110300 |e 110000PL122670008X |e 110300PL122670008X |k 0/110000/ |k 1/110000/110300/ |p 3 | ||
| 999 | |a KXP-PPN1770928952 |e 3979256987 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"origin":[{"dateIssuedDisp":"June 9, 2021","dateIssuedKey":"2021"}],"id":{"eki":["1770928952"],"doi":["10.1137/19M1283951"]},"name":{"displayForm":["Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni"]},"physDesc":[{"extent":"14 S."}],"relHost":[{"title":[{"title":"SIAM journal on discrete mathematics","title_sort":"SIAM journal on discrete mathematics"}],"pubHistory":["1.1988 -"],"titleAlt":[{"title":"Journal on discrete mathematics"}],"part":{"extent":"14","volume":"35","text":"35(2021), 2, Seite 1238-1251","issue":"2","pages":"1238-1251","year":"2021"},"disp":"Society for Industrial and Applied MathematicsSIAM journal on discrete mathematics","note":["Gesehen am 28.06.2021"],"type":{"bibl":"periodical","media":"Online-Ressource"},"recId":"26688539X","language":["eng"],"corporate":[{"role":"aut","roleDisplay":"VerfasserIn","display":"Society for Industrial and Applied Mathematics"}],"origin":[{"publisherPlace":"Philadelphia, Pa.","dateIssuedKey":"1988","publisher":"Soc.","dateIssuedDisp":"1988-"}],"id":{"issn":["1095-7146"],"zdb":["1468404-4"],"eki":["26688539X"]},"name":{"displayForm":["Society for Industrial and Applied Mathematics"]},"physDesc":[{"extent":"Online-Ressource"}]}],"title":[{"title":"On the query complexity of estimating the distance to hereditary graph properties","title_sort":"On the query complexity of estimating the distance to hereditary graph properties"}],"person":[{"given":"Carlos","family":"Hoppen","role":"aut","roleDisplay":"VerfasserIn","display":"Hoppen, Carlos"},{"display":"Kohayakawa, Yoshiharu","roleDisplay":"VerfasserIn","role":"aut","family":"Kohayakawa","given":"Yoshiharu"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Lang, Richard","given":"Richard","family":"Lang"},{"family":"Lefmann","given":"Hanno","roleDisplay":"VerfasserIn","display":"Lefmann, Hanno","role":"aut"},{"family":"Stagni","given":"Henrique","roleDisplay":"VerfasserIn","display":"Stagni, Henrique","role":"aut"}],"note":["Gesehen am 19.09.2021"],"type":{"bibl":"article-journal","media":"Online-Ressource"},"recId":"1770928952","language":["eng"]} | ||
| SRT | |a HOPPENCARLONTHEQUERY9202 | ||