Abstract
The \(\mathsf {NP}\)-complete graph problem Cluster Editing seeks to transform a static graph into disjoint union of cliques by making the fewest possible edits to the edge set. We introduce a natural interpretation of this problem in the setting of temporal graphs, whose edge-sets are subject to discrete changes over time, which we call Editing to Temporal Cliques. This problem is \(\mathsf {NP}\)-complete even when restricted to temporal graphs whose underlying graph is a path, but we obtain two polynomial-time algorithms for special cases with further restrictions. In the static setting, it is well-known that a graph is a disjoint union of cliques if and only if it contains no induced copy of \(P_3\); we demonstrate that there can be no universal characterisation of cluster temporal graphs in terms of subsets of at most four vertices. However, subject to a minor additional restriction, we obtain a characterisation involving forbidden configurations on five vertices. This characterisation gives rise to an \(\mathsf {FPT}\) algorithm parameterised simultaneously by the permitted number of modifications and the lifetime of the temporal graph, which uses a simple search-tree strategy.
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
Abu-Khzam, F.N.: The multi-parameterized cluster editing problem. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 284–294. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03780-6_25
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004)
Bartier, V., Bathie, G., Bousquet, N., Heinrich, M., Pierron, T., Prieto, U.: PACE solver description: \(\mu \)solver - heuristic track. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, 8–10 September 2021, Lisbon, Portugal, volume 214 of LIPIcs, pp. 33:1–33:3. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
Bocci, C., Capresi, C., Meeks, K., Sylvester, J.: A new temporal interpretation of cluster editing. CoRR, abs/2202.01103 (2022)
Böcker, S., Baumbach, J.: Cluster editing. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 33–44. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39053-1_5
Böcker, S.: A golden ratio parameterized algorithm for cluster editing. J. Discrete Algorithms 16, 79–89 (2012). Selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011)
Cao, Y., Chen, J.: Cluster editing: kernelization based on edge cuts. Algorithmica 64(1), 152–169 (2012)
Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. J. Comput. Syst. Sci. 78(1), 211–220 (2012)
Chen, J., Molter, H., Sorge, M., Suchý, O.: Cluster editing in multi-layer and temporal graphs. In: Hsu, W.-L., Lee, D.-T., Liao, C.-S. (eds.) 29th International Symposium on Algorithms and Computation, ISAAC 2018, 16–19 December 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pp. 24:1–24:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Delvaux, S., Horsten, L.: On best transitive approximations to simple graphs. Acta Inform. 40(9), 637–655 (2004)
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)
Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M.: Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min. 7(1), 35:1–35:16 (2017)
Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discret. Appl. Math. 160(15), 2259–2270 (2012)
Krivánek, M., Morávek, J.: NP -hard problems in hierarchical-tree clustering. Acta Inform. 23(3), 311–323 (1986)
Li, S., Pilipczuk, M., Sorge, M.: Cluster editing parameterized above modification-disjoint \(P_3\)-packings. In: Bläser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, 16–19 March 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pp. 49:1–49:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
Luo, J., Molter, H., Nichterlein, A., Niedermeier, R.: Parameterized dynamic cluster editing. Algorithmica 83(1), 1–44 (2021)
Mannaa, B.: Cluster editing problem for points on the real line: a polynomial time algorithm. Inf. Process. Lett. 110(21), 961–965 (2010)
Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V., Zschoche, P.: Computing maximum matchings in temporal graphs. In: Paul, C., Bläser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, 10–13 March 2020, Montpellier, France, volume 154 of LIPIcs, pp. 27:1–27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discret. Appl. Math. 144(1–2), 173–182 (2004)
Viard, T., Latapy, M., Magnien, C.: Computing maximal cliques in link streams. Theor. Comput. Sci. 609, 245–252 (2016)
Yang, Z., Algesheimer, R., Tessone, C.J.: A comparative analysis of community detection algorithms on artificial networks. Sci. Rep. 6, article no. 30750 (2016)
Acknowledgements
Meeks and Sylvester gratefully acknowledge funding from the Engineering and Physical Sciences Research Council (ESPRC) grant number EP/T004878/1 for this work, while Meeks was also supported by a Royal Society of Edinburgh Personal Research Fellowship (funded by the Scottish Government).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Bocci, C., Capresi, C., Meeks, K., Sylvester, J. (2022). A New Temporal Interpretation of Cluster Editing. In: Bazgan, C., Fernau, H. (eds) Combinatorial Algorithms. IWOCA 2022. Lecture Notes in Computer Science, vol 13270. Springer, Cham. https://doi.org/10.1007/978-3-031-06678-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-06678-8_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-06677-1
Online ISBN: 978-3-031-06678-8
eBook Packages: Computer ScienceComputer Science (R0)