Maximum Bipartite Subgraph of Geometric Intersection Graphs
share
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(nlog n)-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 that runs in in O(f(n) n^1/ϵ) time for any ϵ>0,where f(n) is a computable function that is polynomial in n. 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 (TFS), 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).
READ FULL TEXT