Fast Algorithms for Max Cut on Geometric Intersection Graphs

Abstract

In this work, we design fast algorithms for max cut on geometric intersection graphs. In the maximum cut (a.k.a., max cut) problem, the input is an undirected graph, and the goal is to partition the vertex set into two disjoint sets such that the number of edges having their endpoints in different sets is maximized. In a geometric intersection graph, given a collection of n geometric objects as input (say unit intervals or unit squares), each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. Note that the edge-set of the graph is not explicitly given as input. A simple O(n) time algorithm places each object randomly into one of the two sets to achieve a 0.5 approximation. Our goal is to design near-linear time algorithms (in terms of n) and beat the 0.5 approximation barrier. We obtain the following results: • An O(nlogn) time algorithm with an approximation factor of 2/3 for unit interval in- tersection graphs. We decompose the unit intervals into several cliques and based on the number of edges between “adjacent” cliques, we choose an appropriate partitioning strategy. • An O(nlogn) time algorithm with an approximation factor of 7/13 for unit square in- tersection graphs. We iteratively find the deepest point among the unit squares and then remove the squares containing the deepest point. To obtain a fast algorithm, we design a data structure which can efficiently answer deepest point queries and also, efficiently handle deletion of unit squares. • An exact and fast algorithm for laminar geometric intersection graphs. Our algorithm uses a simple greedy strategy; however, proving its correctness requires non-trivial ideas. A fast algorithm is obtained by combining the properties of laminar objects with range searching data structures.