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’⊆ S such that the intersection graph of the objects in S’ is bipartite. We first 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 algorithmic side, we first give a simple O(n)-time algorithm that solves the MBS problem on a set of n intervals. Then, we give an O(n2)-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 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 (MTFS), where the objective is the same as that of MBS except the intersection graph induced by the set S’ needs to be triangle-free only (instead of being bipartite).

Additional Metadata
Keywords Approximation schemes, Bipartite subgraph, Geometric intersection graphs, NP-hardness, Triangle-free subgraph
Persistent URL dx.doi.org/10.1007/978-3-030-39881-1_14
Series Lecture Notes in Computer Science
Citation
Jana, S. (Satyabrata), Maheshwari, A, Mehrabi, S. (Saeed), & Roy, S. (Sasanka). (2020). Maximum bipartite subgraph of geometric intersection graphs. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-39881-1_14