Document Open Access Logo

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error

Authors Hendrik Fichtenberger , Reut Levi , Yadu Vasudev , Maximilian Wötzel

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.52.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • graph property testing
  • minor-free graphs

Metrics

Abstract

We consider one-sided error property testing of F-minor freeness in bounded-degree graphs for any finite family of graphs F that contains a minor of K_{2,k}, the k-circus graph, or the (k x 2)-grid for any k in N. This includes, for instance, testing whether a graph is outerplanar or a cactus graph. The query complexity of our algorithm in terms of the number of vertices in the graph, n, is O~(n^{2/3} / epsilon^5). Czumaj et al. (2014) showed that cycle-freeness and C_k-minor freeness can be tested with query complexity O~(sqrt{n}) by using random walks, and that testing H-minor freeness for any H that contains a cycles requires Omega(sqrt{n}) queries. In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor H, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, which induces an H-minor.

Cite As Get BibTex

Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian Wötzel. A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.52

Author Details

Hendrik Fichtenberger
  • TU Dortmund, Dortmund, Germany
Reut Levi
  • Weizmann Institute of Science, Rehovot, Israel
Yadu Vasudev
  • Indian Institute of Technology Madras, Chennai, India
Maximilian Wötzel
  • BGSMath and UPC Barcelona, Barcelona, Spain

Funding

  • Fichtenberger, Hendrik: Supported by ERC grant no 307696.
  • Levi, Reut: Supported by ERC-CoG grant 772839.
  • Vasudev, Yadu: Supported by ERC grant no 307696.
  • Wötzel, Maximilian: Supported by ERC grant no 307696, the Spanish Ministerio de Economía y Competitividad projects MTM2014-54745-P, MTM2017-82166-P and an FPI grant under the María de Maetzu research grant MDM-2014-0445.

References

  1. I. Benjamini, O. Schramm, and A. Shapira. Every minor-closed property of sparse graphs is testable. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC), pages 393-402, 2008. URL: http://dx.doi.org/10.1145/1374376.1374433.
  2. H. L. Bodlaender. On Linear Time Minor Tests with Depth-First Search. Journal of Algorithms, 14(1):1-23, 1993. URL: http://dx.doi.org/10.1006/jagm.1993.1001.
  3. A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler. Finding cycles and trees in sublinear time. Random Structure and Algorithms, 45(2):139-184, 2014. URL: http://dx.doi.org/10.1002/rsa.20462.
  4. A. Czumaj, A. Shapira, and C. Sohler. Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM Journal on Computing, 38(6):2499-2510, 2009. URL: http://dx.doi.org/10.1137/070681831.
  5. M. Elkin and O. Neiman. Efficient algorithms for constructing very sparse spanners and emulators. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 652-669, 2017. Google Scholar
  6. P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  7. H. Fichtenberger, R. Levi, Y. Vasudev, and M. Wötzel. A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error. arXiv:1707.06126, 2018. URL: http://arxiv.org/abs/1707.06126.
  8. O. Goldreich. Introduction to testing graph properties. In Property Testing, pages 105-141. Springer, 2010. URL: http://link.springer.com/chapter/10.1007/978-3-642-16367-8_7.
  9. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  10. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  11. O. Goldreich and D. Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica, 19(3):335-373, 1999. URL: http://dx.doi.org/10.1007/s004930050060.
  12. O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0078-7.
  13. A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and testing. In Proceedings of the Fiftieth Annual Symposium on Foundations of Computer Science (FOCS), pages 22-31, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.77.
  14. C. Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15(1):271-283, 1930. URL: http://eudml.org/doc/212352.
  15. C. Lenzen and R. Levi. A local algorithm for the sparse spanning graph problem. arXiv:1703.05418, 2017. URL: http://arxiv.org/abs/1703.05418.
  16. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms, 11(3):24:1-24:13, 2015. Google Scholar
  17. N. Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: http://dx.doi.org/10.1016/j.jctb.2004.08.001.
  18. K. Wagner. über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114(1):570-590, 1937. URL: http://dx.doi.org/10.1007/BF01594196.
  19. Y. Yoshida and H. Ito. Testing outerplanarity of bounded degree graphs. Algorithmica, 73(1):1-20, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9897-1.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact