Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-184 | 28th December 2022 16:23

Testing in the bounded-degree graph model with degree bound two

RSS-Feed




TR22-184
Authors: Oded Goldreich, Laliv Tauber
Publication: 28th December 2022 16:24
Downloads: 229
Keywords: 


Abstract:

Considering the bounded-degree graph model, we show that if the degree bound is two,
then every graph property can be tested within query complexity that only depends on the proximity parameter.
Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.
The key observation is that a graph of maximum degree two consists of a collection of paths and cycles,
and that a collection of long paths and cycles is relatively close (in this model) to a single cycle.



ISSN 1433-8092 | Imprint