Document Open Access Logo

A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs

Authors Utkarsh Joshi, Saladi Rahul, Josson Joe Thoppil

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.21.pdf
  • Filesize: 0.83 MB
  • 12 pages

Document Identifiers

Author Details

Utkarsh Joshi
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Saladi Rahul
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Josson Joe Thoppil
  • Department of Information Technology, National Institute of Technology, Karnataka, India

Cite AsGet BibTex

Utkarsh Joshi, Saladi Rahul, and Josson Joe Thoppil. A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.21

Abstract

In a geometric intersection graph, given a collection of n geometric objects as input, each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. In this work, we present a somewhat surprising result: a polynomial time algorithm for max cut on laminar geometric intersection graphs. In a laminar geometric intersection graph, if two objects intersect, then one of them will completely lie inside the other. To the best of our knowledge, for max cut this is the first class of (non-trivial) geometric intersection graphs with an exact solution in polynomial time. Our algorithm uses a simple greedy strategy. However, proving its correctness requires non-trivial ideas. Next, we design almost-linear time algorithms (in terms of n) for laminar axis-aligned boxes by combining the properties of laminar objects with vertical ray shooting data structures. Note that the edge-set of the graph is not explicitly given as input; only the n geometric objects are given as input.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Graph algorithms analysis
Keywords
  • Geometric intersection graphs
  • Max cut
  • Vertical ray shooting

Metrics

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

References

  1. Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of maximum cut on interval graphs. In 37th International Symposium on Computational Geometry (SoCG), volume 189, pages 7:1-7:11, 2021. Google Scholar
  2. Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, pages 1-56, 1998. Google Scholar
  3. Francisco Barahona. The max-cut problem on graphs not contractible to k5. Operations Research Letters, 2(3):107-111, 1983. Google Scholar
  4. Alexey Barsukov, Kaustav Bose, and Bodhayan Roy. Maximum cut on interval graphs of interval count two is np-complete. Computing Research Repository (CoRR), abs/2203.06630, 2022. Google Scholar
  5. Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pages 200-209, 1999. Google Scholar
  6. Hans L. Bodlaender, Celina M. H. de Figueiredo, Marisa Gutierrez, Ton Kloks, and Rolf Niedermeier. Simple max-cut for split-indifference graphs and graphs with few p4’s. In Experimental and Efficient Algorithms, pages 87-99, 2004. Google Scholar
  7. Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1):14-31, 2000. Google Scholar
  8. Hans L. Bodlaender, Ton Kloks, and Rolf Niedermeier. Simple max-cut for unit interval graphs and graphs with few p4s. Electronic Notes in Discrete Mathematics, 3:19-26, 1999. Google Scholar
  9. Arman Boyacı, Tinaz Ekim, and Mordechai Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29-33, 2017. Google Scholar
  10. Arman Boyacı, Tınaz Ekim, and Mordechai Shalom. The maximum cardinality cut problem in co-bipartite chain graphs. Journal of Combinatorial Optimization, 35(1):250-265, 2018. Google Scholar
  11. Timothy M. Chan. Persistent Predecessor Search and Orthogonal Point Location on the Word RAM. ACM Trans. Algorithms, 9(3), 2013. Google Scholar
  12. Timothy M. Chan and Konstantinos Tsakalidis. Dynamic Planar Orthogonal Point Location in Sublogarithmic Time. In 34th International Symposium on Computational Geometry (SoCG 2018), volume 99, pages 25:1-25:15, 2018. Google Scholar
  13. Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck’s inequality. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 54-60, 2004. Google Scholar
  14. Celina M. H. de Figueiredo, Alexsander Andrade de Melo, Fabiano de S. Oliveira, and Ana Silva. Maxcut on permutation graphs is np-complete. Computing Research Repository (CoRR), abs/2202.13955, 2022. Google Scholar
  15. Celina MH de Figueiredo, Alexsander A de Melo, Fabiano S Oliveira, and Ana Silva. Maximum cut on interval graphs of interval count four is np-complete. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.09804.
  16. Josep Díaz and Marcin Kamiński. Max-cut and max-bisection are NP-hard on unit disk graphs. Theoretical Computer Science, 377(1):271-276, 2007. Google Scholar
  17. M. X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115-1145, 1995. Google Scholar
  18. Venkatesan Guruswami. Maximum cut on line and total graphs. Discrete Applied Mathematics, 92(2):217-221, 1999. Google Scholar
  19. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal of Computing, 4(3):221-225, 1975. Google Scholar
  20. Yijie Han. Deterministic sorting in o(nloglogn) time and linear space. Journal of Algorithms, 50(1):96-105, 2004. Google Scholar
  21. Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel. Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. SIAM Journal of Computing, 35(1):110-119, 2005. Google Scholar
  22. David S Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 6(3):434-451, 1985. Google Scholar
  23. Satyen Kale and C. Seshadhri. Combinatorial approximation algorithms for maxcut using random walks. In Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), pages 367-388, 2011. Google Scholar
  24. Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  25. Jan Kratochvíl, Tomáš Masařík, and Jana Novotná. U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170, pages 57:1-57:14, 2020. Google Scholar
  26. Luca Trevisan. Max cut and the smallest eigenvalue. SIAM Journal of Computing, 41(6):1769-1786, 2012. Google Scholar
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