Maximum Bipartite Subgraph of Geometric Intersection Graphs

DOI10.1007/978-3-030-39881-1_14arXiv1909.03896MaRDI QIDQ6324943FDOQ6324943

Authors: Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi, Sasanka Roy 

Publication date: 9 September 2019

Abstract: We study the Maximum Bipartite Subgraph (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^{\prime }subseteqS$ such that the intersection graph of the objects in $S^{\prime }$ is bipartite. We first give a simple $O(n)$-time algorithm that solves the MBS problem on a set of $n$ intervals. We also give an $O(n^2)$-time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. We show that the MBS problem is NP-hard on geometric graphs for which the maximum independent set is NP-hard (hence, it is NP-hard even on unit squares and unit disks). On the other hand, we give a PTAS for the problem on unit squares and unit disks. Moreover, we show fast 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 (TFS), where the objective is the same as that of MBS except the intersection graph induced by the set $S^{\prime }$ needs to be triangle-free only (instead of being bipartite).

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Maximum Bipartite Subgraph of Geometric Intersection Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6324943)