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

#### Webpage for a paper by Oded Goldreich and Laliv Tauber

#### 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.

#### Material available on-line

- First version posted:
Dec 2022.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.