DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.21

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

Authors: Utkarsh Joshi, Saladi Rahul, and Josson Joe Thoppil

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{joshi_et_al:LIPIcs.FSTTCS.2022.21,
  author =	{Joshi, Utkarsh and Rahul, Saladi and Thoppil, Josson Joe},
  title =	{{A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.21},
  URN =		{urn:nbn:de:0030-drops-174139},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.21},
  annote =	{Keywords: Geometric intersection graphs, Max cut, Vertical ray shooting}
}

Search Results

Documents authored by Thoppil, Josson Joe

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

Abstract

Cite as

Thanks for your feedback!

Could not send message