(This is a revised version of work that was posted on arXiv in July 2010.)
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/\epsilon)\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 $\epsilon$.
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 $\epsilon$.
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.
Various (small) corrections
(This is a revised version of work that was posted on arXiv in July 2010.)
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/\epsilon)\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 $\epsilon$.
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 $\epsilon$.
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.
Being on the editorial board of ECCC, I feel that I should relate to the question of why this work is posted on ECCC at all and why it was not posted before.
Initially, my feeling was that this work is not really in scope, and so I objected its posting on ECCC. However, in retrospect, I feel that I was too strict wrt scope. Firstly, on the technical level, the work does contain a section which establishes a lower bound. But more importantly, this work seems to explicitly initiate a study of a natural type of search problems (i.e., problems concerned with finding small structures in graphs that are "far" from lacking such structures).
