Abstract
We study the
(shortly,
) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a
graph \(G=(V,E)\), where each vertex in V is colored with either “
” or “
”, the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is
, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for the
problem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs.
S. Bhore—The author is supported by the Austrian Science Fund (FWF) grant P 31119.
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
Notes
- 1.
Some results are described in the full version, because of page limitations here.
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Bhore, S., Chakraborty, S., Jana, S., Mitchell, J.S.B., Pandit, S., Roy, S.: The balanced connected subgraph problem. In: Pal, S.P., Vijayakumar, A. (eds.) CALDAM 2019. LNCS, vol. 11394, pp. 201–215. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11509-8_17
Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Quadratic kernelization for convex recoloring of trees. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 86–96. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73545-8_11
Bodlaender, H.L., Fellows, M.R., Warnow, T.J.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 273–283. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55719-9_80
Bodlaender, H.L., de Fluiter, B.: Intervalizing k-colored graphs. In: Fülöp, Z., Gécseg, F. (eds.) ICALP 1995. LNCS, vol. 944, pp. 87–98. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60084-1_65
Bonnet, É., Sikora, F.: The graph motif problem parameterized by the structure of the input graph. Discret. Appl. Math. 231, 78–94 (2017)
Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799–811 (2011)
Fellows, M.R., Hallett, M.T., Wareham, H.T.: DNA physical mapping: three ways difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 157–168. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57273-2_52
Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
Kikuno, T., Yoshida, N., Kakuda, Y.: The NP-completeness of the dominating set problem in cubic planer graphs. IEICI Trans. (1976–1990) 63(6), 443–444 (1980)
Lacroix, V., Fernandes, C.G., Sagot, M.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 360–368 (2006)
Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. (TCBB) 3(4), 360–368 (2006)
Acknowledgement
We thank Joseph S. B. Mitchell for his useful suggestions.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Bhore, S., Jana, S., Pandit, S., Roy, S. (2019). Balanced Connected Subgraph Problem in Geometric Intersection Graphs. In: Li, Y., Cardei, M., Huang, Y. (eds) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science(), vol 11949. Springer, Cham. https://doi.org/10.1007/978-3-030-36412-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-36412-0_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36411-3
Online ISBN: 978-3-030-36412-0
eBook Packages: Computer ScienceComputer Science (R0)