Abstract
We study the parameterized complexity of the \(s\)-Club Cluster Edge Deletion problem: Given a graph G and two integers \(s \ge 2\) and \(k \ge 1\), is it possible to remove at most k edges from G such that each connected component of the resulting graph has diameter at most s? This problem is known to be \(\texttt{NP}\)-hard already when \(s = 2\).We prove that it admits a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The same result easily transfers to the case in which we can remove at most k vertices, rather than k edges, from G such that each connected component of the resulting graph has diameter at most s, namely to \(s\)-Club Cluster Vertex Deletion.
This work was partially supported by: (i) MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for HArnessing networked Data”; (ii) University of Perugia, Fondi di Ricerca di Ateneo, edizione 2021, project “AIDMIX - Artificial Intelligence for Decision making: Methods for Interpretability and eXplainability”.
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.
Since the matrix is symmetric, when we update a cell \(D({\partial {C}})[a,b]\) we assume that also \(D({\partial {C}})[b,a]\) is updated with the same value.
References
Abu-Khzam, F.N., Makarem, N., Shehab, M.: An improved fixed-parameter algorithm for 2-club cluster edge deletion. CoRR. arXiv:2107.01133 (2021)
Alba, R.: A graph-theoretic definition of a sociometric clique. J. Math. Soc. 3, 113–126 (1973). https://doi.org/10.1080/0022250X.1973.9989826
Balasundaram, B., Butenko, S., Trukhanov, S.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10(1), 23–39 (2005). https://doi.org/10.1007/s10878-005-1857-x
Balasundaram, B., Pajouh, F.M.: Graph theoretic clique relaxations and applications. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 1559–1598. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1_9
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004). https://doi.org/10.1023/B:MACH.0000033116.57574.95
Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3/4), 281–297 (1999). https://doi.org/10.1089/106652799318274
Böcker, S.: A golden ratio parameterized algorithm for cluster editing. J. Discrete Algorithms 16, 79–89 (2012). https://doi.org/10.1016/j.jda.2012.04.005
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996). https://doi.org/10.1137/S0097539793251219
Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358–402 (1996). https://doi.org/10.1006/jagm.1996.0049
Chakraborty, D., Chandran, L.S., Padinhatteeri, S., Pillai, R.R.: Algorithms and complexity of s-club cluster vertex deletion. In: Flocchini, P., Moura, L. (eds.) IWOCA 2021. LNCS, vol. 12757, pp. 152–164. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79987-8_11
Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. J. Comput. Syst. Sci. 78(1), 211–220 (2012). https://doi.org/10.1016/j.jcss.2011.04.001
Dondi, R., Lafond, M.: On the tractability of covering a graph with 2-clubs. In: Gąsieniec, L.A., Jansson, J., Levcopoulos, C. (eds.) FCT 2019. LNCS, vol. 11651, pp. 243–257. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25027-0_17
Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science, 1st Edition. Springer (1999). https://doi.org/10.1007/978-1-4612-0515-9
Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci. 80(7), 1430–1447 (2014). https://doi.org/10.1016/j.jcss.2014.04.015
Kloks, T. (ed.): Treewidth. LNCS, vol. 842. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0045375
Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (2016). https://doi.org/10.3390/a9010021
Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discret. Appl. Math. 160(15), 2259–2270 (2012). https://doi.org/10.1016/j.dam.2012.05.019
Laan, S., Marx, M., Mokken, R.J.: Close communities in social networks: boroughs and 2-clubs. Soc. Netw. Anal. Min. 6(1), 1–16 (2016). https://doi.org/10.1007/s13278-016-0326-0
Liu, H., Zhang, P., Zhu, D.: On editing graphs into 2-club clusters. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM/FAW -2012. LNCS, vol. 7285, pp. 235–246. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29700-7_22
Misra, N., Panolan, F., Saurabh, S.: Subexponential algorithm for d-cluster edge deletion: exception or rule? J. Comput. Syst. Sci. 113, 150–162 (2020). https://doi.org/10.1016/j.jcss.2020.05.008
Mokken, R.: Cliques, clubs and clans. Qual. Quan. Int. J. Methodol. 13(2), 161–173 (1979). https://doi.org/10.1007/BF00139635
Mokken, R.J., Heemskerk, E.M., Laan, S.: Close communication and 2-clubs in corporate networks: europe 2010. Soc. Netw. Anal. Min. 6(1), 1–19 (2016). https://doi.org/10.1007/s13278-016-0345-x
Montecchiani, F., Ortali, G., Piselli, T., Tappini, A.: On the parameterized complexity of the s-club cluster edge deletion problem. CoRR. arXiv:2205.10834 (2022)
Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)
Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27–64 (2007). https://doi.org/10.1016/j.cosrev.2007.05.001
Schäfer, A.: Exact algorithms for \(s\)-club finding and related problems. Diploma thesis, Friedrich-Schiller-Universität Jena (2009)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144(1–2), 173–182 (2004). https://doi.org/10.1016/j.dam.2004.01.007
Wu, Z., Leahy, R.M.: An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 15(11), 1101–1113 (1993). https://doi.org/10.1109/34.244673
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Montecchiani, F., Ortali, G., Piselli, T., Tappini, A. (2023). On the Parameterized Complexity of s-club Cluster Deletion Problems. In: Gąsieniec, L. (eds) SOFSEM 2023: Theory and Practice of Computer Science. SOFSEM 2023. Lecture Notes in Computer Science, vol 13878. Springer, Cham. https://doi.org/10.1007/978-3-031-23101-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-23101-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-23100-1
Online ISBN: 978-3-031-23101-8
eBook Packages: Computer ScienceComputer Science (R0)