We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Maximum Bipartite Subgraphs of Geometric Intersection Graphs.
- Authors
Jana, Satyabrata; Maheshwari, Anil; Mehrabi, Saeed; Roy, Sasanka
- Abstract
We study the Maximum Bipartite Subgraph (M B S) 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 give an O (n 2) -time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the M B S problem is N P -hard on geometric graphs for which the maximum independent set is N P -hard (hence, it is N P -hard even on unit squares and unit disks). On the other hand, we give a P T A S 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 axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph (M T F S) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the M B S except the intersection graph induced by the set S ′ needs to be triangle-free only (instead of being bipartite).
- Subjects
INTERSECTION graph theory; BIPARTITE graphs; SUBGRAPHS; APPROXIMATION algorithms; INDEPENDENT sets; NP-hard problems
- Publication
International Journal of Computational Geometry & Applications, 2023, Vol 33, Issue 3/4, p133
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S021819592350005X