๐ฎ
๐ฎ
The Ethereal
On the query complexity of estimating the distance to hereditary graph properties
December 02, 2019 ยท The Ethereal ยท ๐ SIAM Journal on Discrete Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, Henrique Stagni
arXiv ID
1912.01081
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
5
Venue
SIAM Journal on Discrete Mathematics
Last Checked
6 months ago
Abstract
Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $ฮ$ 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}$.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal