Finding cycles and trees in sublinear time

DOI10.1002/RSA.20462MaRDI QIDQ2925521zbMATH OpenOpenAlexWikidataFDO

Authors Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler, Artur Czumaj

Publication date 16 October 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.4230

zbMATH Keywords

bounded-degree graphsone-sided versus two-sided error probabilityproperty testingsublinear-time algorithms

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Abstract: We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $kgeq3$ 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, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time $ildeO(sqrtN)$, 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} property testing algorithms 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 $ildeO(poly(1/e)cdotsqrtN)$. This matches the known $Omega(sqrtN)$ 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 $kgeq3$, 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(sqrtN)$ complexity.

Review text

This paper presents sublinear-time (randomized) algorithms for finding simple cycles of length at least \(k\geq 3\) 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, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time \(\tilde O(\sqrt{N})\), where \(N\) denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors.

Recommendations

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
• Color-coding

Cites work

• A sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• Expanding graphs contain all small trees
• Finding cycles and trees in sublinear time
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• On the girth of hamiltonian weakly pancyclic graphs
• On the randomness complexity of property testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Testing satisfiability
• Testing the diameter of graphs
• The disjoint paths problem in quadratic time
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(17)

• Stability structures of conjunctive Boolean networks
• Non-interactive proofs of proximity
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Property testing of planarity in the \textsf{CONGEST} model
• Finding cycles and trees in sublinear time
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Finding even cycles faster via capped k-walks
• A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Find subtrees of specified weight and cycles of specified length in linear time
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Testing C_k-freeness in bounded-arboricity graphs
• Sublinear time algorithms in the theory of groups and semigroups.
• Results on H-freeness testing in graphs of bounded r-admissibility
• Testing depth first search numbering

This page was built for publication: Finding cycles and trees in sublinear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2925521)