Document Open Access Logo

Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs

Authors Chetan Gupta, Rahul Jain , Raghunath Tewari

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.23.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Chetan Gupta
  • Aalto University, Finland
Rahul Jain
  • Fernuniversität in Hagen, Germany
Raghunath Tewari
  • Indian Institute of Technology Kanpur, India

Funding

  • Gupta, Chetan: Academy of Finland Grant 321901 and Visvesvaraya PhD Grant.
  • Tewari, Raghunath: DST Inspire Faculty Grant and Visvesvaraya Young Faculty Fellowship.

Cite AsGet BibTex

Chetan Gupta, Rahul Jain, and Raghunath Tewari. Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.23

Abstract

A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial-time algorithm that uses O(g^{1/2} n^{1/2} log n)-space to find an O(g^{1/2} n^{1/2})-sized separator of a graph having n vertices and embedded on an orientable surface of genus g.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph algorithms
  • space-bounded algorithms
  • surface embedded graphs
  • reachability
  • Euler genus
  • algorithmic graph theory
  • computational complexity theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Eric Allender, Samir Datta, and Sambuddha Roy. The directed planar reachability problem. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, pages 238-249, 2005. URL: https://doi.org/10.1007/11590156_19.
  2. Eric Allender and Meena Mahajan. The complexity of planarity testing. Information and Computation, 189(1):117-134, 2004. URL: https://doi.org/10.1016/j.ic.2003.09.002.
  3. Ryo Ashida, Tomoaki Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, and Osamu Watanabe. A sublinear-space and polynomial-time separator algorithm for planar graphs. Electronic Colloquium on Computational Complexity (ECCC), 26:91, 2019. Google Scholar
  4. Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin F. Yang. New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs. In Proceedings of the 34th Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), pages 585-595, 2014. Google Scholar
  5. Diptarka Chakraborty and Raghunath Tewari. An O(n^ε) space and polynomial time algorithm for reachability in directed layered planar graphs. ACM Transactions on Computation Theory (TOCT), 9(4):19:1-19:11, 2017. Google Scholar
  6. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pages 383-392. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591865.
  7. H. Gazit and G. L. Miller. A parallel algorithm for finding a separator in planar graphs. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS 1987), pages 238-248, October 1987. URL: https://doi.org/10.1109/SFCS.1987.3.
  8. John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, 1984. URL: https://doi.org/10.1016/0196-6774(84)90019-1.
  9. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, and Osamu Watanabe. An O(n^1/2 + ε)-space and polynomial-time algorithm for directed planar reachability. In Proceedings of the 28th Conference on Computational Complexity (CCC 2013), pages 277-286, 2013. Google Scholar
  10. Rahul Jain and Raghunath Tewari. Reachability in High Treewidth Graphs. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), 2019. Google Scholar
  11. Ioannis Koutis and Gary L. Miller. A linear work, O(n^1/6) time, parallel algorithm for solving planar laplacians. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 1002-1011, 2007. Google Scholar
  12. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: https://doi.org/10.1137/0136016.
  13. B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001. URL: https://books.google.com.sg/books?id=_VFKscYKSicC.
  14. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):17, 2008. Google Scholar
  15. Carsten Thomassen. Embeddings of graphs with no short noncontractible cycles. Journal of Combinatorial Theory, Series B, 48(2):155-177, 1990. URL: https://doi.org/10.1016/0095-8956(90)90115-G.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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