2020 | OriginalPaper | Chapter
Maximum Bipartite Subgraph of Geometric Intersection Graphs
Authors : Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi, Sasanka Roy
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
MBS
) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset \(S'\subseteq S\) such that the intersection graph of the objects in \(S'\) is bipartite. We first show that the \(\texttt {MBS}\) problem is \(\texttt {NP}\)-hard on geometric graphs for which the maximum independent set is \(\texttt {NP}\)-hard (hence, it is \(\texttt {NP}\)-hard even on unit squares and unit disks). On the algorithmic side, we first give a simple \(\mathcal {O}(n)\)-time algorithm that solves the \(\texttt {MBS}\) problem on a set of n intervals. Then, we give an \(\mathcal {O}(n^2)\)-time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. Moreover, for the approximability of the problem, we first present a \(\texttt {PTAS}\) for the problem on unit squares and unit disks. Then, we present efficient approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (\({{\texttt {\textit{MTFS}}}}\)), where the objective is the same as that of \(\texttt {MBS}\) except the intersection graph induced by the set \(S'\) needs to be triangle-free only (instead of being bipartite).