Joshi, Utkarsh ;
Rahul, Saladi ;
Thoppil, Josson Joe
A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs
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 (nontrivial) geometric intersection graphs with an exact solution in polynomial time. Our algorithm uses a simple greedy strategy. However, proving its correctness requires nontrivial ideas.
Next, we design almostlinear time algorithms (in terms of n) for laminar axisaligned boxes by combining the properties of laminar objects with vertical ray shooting data structures. Note that the edgeset of the graph is not explicitly given as input; only the n geometric objects are given as input.
BibTeX  Entry
@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:121:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17413},
URN = {urn:nbn:de:0030drops174139},
doi = {10.4230/LIPIcs.FSTTCS.2022.21},
annote = {Keywords: Geometric intersection graphs, Max cut, Vertical ray shooting}
}
14.12.2022
Keywords: 

Geometric intersection graphs, Max cut, Vertical ray shooting 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 