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'\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).
This work is supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aoshima, K., Iri, M.: Comments on F. Hadlock’s paper: finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 6(1), 86 (1977)
Baïou, M., Barahona, F.: Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs. SIAM J. Discrete Math. 30(2), 1290–1301 (2016)
Bose, P., et al.: Computing maximum independent set on outerstring graphs and their relatives. In: Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), Edmonton, AB, Canada (2019)
Brandstädt, A.: On improved time bounds for permutation graph problems. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 1–10. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-56402-0_30
Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, NY, USA, 4–6 January 2009, pp. 892–901 (2009)
Choi, H., Nakajima, K., Rim, C.S.: Graph bipartization and via minimization. SIAM J. Discrete Math. 2(1), 38–47 (1989)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1–3), 165–177 (1990)
Cornaz, D., Mahjoub, A.R.: The maximum induced bipartite subgraph problem with edge weights. SIAM J. Discrete Math. 21(3), 662–675 (2007)
Daniel Liang, Y., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34(5), 337–346 (1997)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman, New York (2002)
Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221–225 (1975)
Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)
Honma, H., Nakajima, Y., Sasaki, A.: An algorithm for the feedback vertex set problem on a normal helly circular-arc graph. J. Comput. Commun. 4(08), 23 (2016)
Jana, S., Maheshwari, A., Mehrabi, S., Roy, S.: Maximum bipartite subgraph of geometric intersection graphs. CoRR abs/1909.03896 (2019)
Kratochvíl, J., Nešetřil, J.: Independent set and clique problems in intersection-defined classes of graphs. Commentationes Mathematicae Universitatis Carolinae 31(1), 85–93 (1990)
Kratsch, D., Müller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discrete Appl. Math. 156(10), 1936–1947 (2008)
Lahiri, A., Mukherjee, J., Subramanian, C.R.: Maximum independent set on \(B_1\)-VPG graphs. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 633–646. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26626-8_46
Lokshtanov, D., Saurabh, S., Sikdar, S.: Simpler parameterized algorithm for OCT. In: Combinatorial Algorithms, 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, 28 June–2 July 2009, Revised Selected Papers. pp. 380–384 (2009)
Lokshtanov, D., Saurabh, S., Wahlström, M.: Subexponential parameterized odd cycle transversal on planar graphs. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, Hyderabad, India, 15–17 December 2012, pp. 424–434 (2012)
Lu, C.L., Tang, C.Y.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inf. Process. Lett. 61(2), 107–111 (1997)
Marx, D.: Efficient approximation schemes for geometric problems? In: 13th Annual European Symposium on Algorithms - ESA 2005, Palma de Mallorca, Spain, 3–6 October 2005, Proceedings, pp. 448–459 (2005)
Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 154–165. Springer, Heidelberg (2006). https://doi.org/10.1007/11847250_14
Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194–200. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46515-7_16
Nandy, S.C., Pandit, S., Roy, S.: Faster approximation for maximum independent set on unit disk graph. Inf. Process. Lett. 127, 58–61 (2017)
Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004)
Rim, C.S., Nakajima, K.: On rectangle intersection and overlap graphs. IEEE Trans. Circ. Syst. I Fundam. Theory Appl. 42(9), 549–553 (1995)
Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 1–3 May 1978, pp. 253–264 (1978)
Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310–327 (1981)
Acknowledgment
We thank Michiel Smid for useful discussions on the problem.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Jana, S., Maheshwari, A., Mehrabi, S., Roy, S. (2020). Maximum Bipartite Subgraph of Geometric Intersection Graphs. In: Rahman, M., Sadakane, K., Sung, WK. (eds) WALCOM: Algorithms and Computation. WALCOM 2020. Lecture Notes in Computer Science(), vol 12049. Springer, Cham. https://doi.org/10.1007/978-3-030-39881-1_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-39881-1_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39880-4
Online ISBN: 978-3-030-39881-1
eBook Packages: Computer ScienceComputer Science (R0)