arXiv preprint ·
Tolerant Testers for Subgraph-Freeness
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.