NOTES ON "FINDING CYCLES AND TREES IN SUBLINEAR TIME"
(OUTLINE OF A SHORT PRESENTATION, FEB 2011)
I'm talking of substructures (e.g., cycles) in graphs.
Sublinear time refers to algorithms with direct access to the graph
(can query the incidence function $f:V(G)\times[d]\to V(G)\cup\{\bot\}$)
1. Finding substructures (e.g., cycles) in sublinear time
is possible only if the graph is "far" from lacking them
(e.g., far from being cycle free). (Ow, cf., the $N$-cycle)
2. Finding substructures vs one-sided error (OSE) testing
of the lack of these substructures; e.g., finding cycles
vs *one-sided error* testers of cycle-freeness.
The subgraph explored by a one-sided error tester *when it rejects*
must contain such a substructure (e.g., a cycle),
and thus the tester implicitly finds such a substructure.
3. Reducing cyclefreeness to bipartitness
(since we have a one-sided error tester for the latter):
A simple randomized reduction, open for deterministic.
4. The bipartite/cyclefree (one-sided error) tester:
The special case of expander graphs.
5. Finding cycles of length at least four.
A reduction to cyclefreeness, blow-ups the graph by $d^2$.
Open: a direct algorithm (which is applicable for large $d$).
6. Finding trees: The cases of $k$-path and $k$-leaf tree.
Open: Can you improve over the straightforward $k$-path finder,
but note that the time complexity "must" be exponential in $k$.
Finding a $k$-leaf tree by scanning $O(k/\eps)$ many vertices.