## Finding Cycles and Trees in Sublinear Time

#### Webpage for a paper by Czumaj, Goldreich, Ron, Seshadhri,
Shapira, and Sohler

#### Abstract

We present sublinear-time (randomized) algorithms
for finding simple cycles of length at least $k\geq3$
and tree-minors in bounded-degree graphs.
The complexity of these algorithms is related to the distance
of the graph from being $C_k$-minor free
(resp., free from having the corresponding tree-minor).
In particular, if the graph is far
(i.e., $\Omega(1)$-far) from being cycle-free,
then the algorithm finds a cycle of polylogarithmic length
in time $\tildeO(\sqrt{N})$,
where $N$ denotes the number of vertices.
This time complexity is optimal up to polylogarithmic factors.

The foregoing results are the outcome of our study of the complexity
of {\em one-sided error}\/ testers in the bounded-degree graphs model.
For example, we show that cycle-freeness of $N$-vertex graphs
can be tested with one-sided error
within time complexity $\tildeO(\poly(1/\e)\cdot\sqrt{N})$.
This matches the known $\Omega(\sqrt{N})$ query lower bound,
and contrasts with the fact that any minor-free property admits
a {\em two-sided error}\/ tester of query complexity that only
depends on the proximity parameter $\e$.
For any constant $k\geq3$, we extend this result to testing
whether the input graph has a simple cycle of length at least~$k$.
On the other hand, for any fixed tree $T$,
we show that $T$-minor freeness has a one-sided error tester
of query complexity that only depends on the proximity parameter $\e$.

Our algorithm for finding cycles in bounded-degree graphs
extends to general graphs, where distances are measured with
respect to the actual number of edges. Such an extension is not
possible with respect to finding tree-minors in $o(\sqrt{N})$
complexity.

#### Material available on-line

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