{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T05:59:10Z","timestamp":1772171950592,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/17"],"award-info":[{"award-number":["NI 369\/17"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a dynamic version of the -hard graph modification problem<jats:sc>Cluster Editing<\/jats:sc>. The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a \u201csimilar\u201d cluster graph that is a solution for a second (\u201csubsequent\u201d) input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (three modification scenarios edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as (parameterized) hardness results, thus (except for three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new \u201csimilar\u201d cluster graph to (1)\u00a0the second input graph and to (2)\u00a0the input cluster graph.<\/jats:p>","DOI":"10.1007\/s00453-020-00746-y","type":"journal-article","created":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T06:02:33Z","timestamp":1595656953000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Parameterized Dynamic Cluster Editing"],"prefix":"10.1007","volume":"83","author":[{"given":"Junjie","family":"Luo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,25]]},"reference":[{"key":"746_CR1","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jda.2017.07.003","volume":"45","author":"FN Abu-Khzam","year":"2017","unstructured":"Abu-Khzam, F.N.: On the complexity of multi-parameterized cluster editing. J. Discrete Algorithms 45, 26\u201334 (2017)","journal-title":"J. Discrete Algorithms"},{"key":"746_CR2","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, F.N., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: On the parameterized complexity of dynamic problems. Theor. Comput. Sci. 607, 426\u2013434 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"746_CR3","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Cai, S., Egan, J., Shaw, P., Wang, K.: Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis. In: Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, volume 10185 of LNCS, pp. 59\u201370. Springer (2017)","DOI":"10.1007\/978-3-319-55911-7_5"},{"key":"746_CR4","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Egan, J., Gaspers, S., Shaw, A., Shaw, P.: Cluster editing with vertex splitting. In: Proceedings of the 5th International Symposium on Combinatorial Optimization, ISCO 2018, volume 10856 of LNCS, pp. 1\u201313. Springer (2018)","DOI":"10.1007\/978-3-319-96151-4_1"},{"key":"746_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56, 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"3\u20134","key":"746_CR6","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/106652799318274","volume":"6","author":"A Ben-Dor","year":"1999","unstructured":"Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3\u20134), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"746_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Proceedings of the 34th Conference on Theory and Practice of Computer Science, SOFSEM 2008, volume 4910 of LNCS, pp. 50\u201365. Springer (2008)","DOI":"10.1007\/978-3-540-77566-9_5"},{"key":"746_CR8","unstructured":"B\u00f6ckenhauer, H., Burjons, E., Raszyk, M., Rossmanith, P.: Reoptimization of parameterized problems. CoRR, abs\/1809.10578 (2018)"},{"key":"746_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6cker, S., Baumbach, J.: Cluster Editing. In: Proceedings of the 9th Conference on Computability in Europe, CiE 2013, volume 7921 of LNCS, pp. 33\u201344. Springer (2013)","DOI":"10.1007\/978-3-642-39053-1_5"},{"issue":"1","key":"746_CR10","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"issue":"1","key":"746_CR11","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/s00453-011-9595-1","volume":"64","author":"Y Cao","year":"2012","unstructured":"Cao, Y., Chen, J.: Cluster editing: kernelization based on edge cuts. Algorithmica 64(1), 152\u2013169 (2012)","journal-title":"Algorithmica"},{"issue":"6","key":"746_CR12","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"746_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.jcss.2011.04.001","volume":"78","author":"J Chen","year":"2012","unstructured":"Chen, J., Meng, J.: A $$2k$$ kernel for the cluster editing problem. J. Comput. Syst. Sci. 78(1), 211\u2013220 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"746_CR14","unstructured":"Chen, J., Molter, H., Sorge, M., Such\u00fd, O.: Cluster editing in multi-layer and temporal graphs. In: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC \u201918), volume 123 of LIPIcs, pp. 24:1\u201324:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"746_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"746_CR16","unstructured":"Dey, T.K., Rossi, A., Sidiropoulos, A.: Temporal clustering. In: Proceedings of the 25th Annual European Symposium on Algorithms, ESA 2017, Volume 87 of LIPIcs, pp. 34:1\u201334:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"11","key":"746_CR17","doi-asserted-by":"publisher","first-page":"5820","DOI":"10.1109\/TSP.2012.2212886","volume":"60","author":"X Dong","year":"2012","unstructured":"Dong, X., Frossard, P., Vandergheynst, P., Nefedov, N.: Clustering with multi-layer graphs: a spectral perspective. IEEE Trans. Signal Process. 60(11), 5820\u20135831 (2012)","journal-title":"IEEE Trans. Signal Process."},{"key":"746_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"4","key":"746_CR19","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1109\/TST.2014.6867515","volume":"19","author":"RG Downey","year":"2014","unstructured":"Downey, R.G., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: Dynamic dominating set and turbo-charging greedy heuristics. Tsinghua Sci. Technol. 19(4), 329\u2013337 (2014)","journal-title":"Tsinghua Sci. Technol."},{"issue":"1","key":"746_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"746_CR21","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.jcss.2011.10.003","volume":"78","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Villanger, Y.: Local search: Is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707\u2013719 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"746_CR22","volume-title":"Parameterized Complexity Theory, Volume XIV of Texts in Theoretical Computer Science, An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, Volume XIV of Texts in Theoretical Computer Science, An EATCS Series. Springer, Berlin (2006)"},{"issue":"7","key":"746_CR23","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1016\/j.jcss.2014.04.015","volume":"80","author":"FV Fomin","year":"2014","unstructured":"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\u20131447 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"746_CR24","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"746_CR25","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Kim, E.J., Ordyniak, S., Saurabh, S., Szeider, S.: Don\u2019t be strict in local search! In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pp. 486\u2013492. AAAI Press (2012)","DOI":"10.1609\/aaai.v26i1.8128"},{"issue":"4","key":"746_CR26","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"8\u201310","key":"746_CR27","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/j.tcs.2008.10.021","volume":"410","author":"J Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for cluster editing. Theor. Comput. Sci. 410(8\u201310), 718\u2013726 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"746_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00453-012-9685-8","volume":"67","author":"J Guo","year":"2013","unstructured":"Guo, J., Hartung, S., Niedermeier, R., Such\u00fd, O.: The parameterized complexity of local search for TSP, more refined. Algorithmica 67(1), 89\u2013110 (2013)","journal-title":"Algorithmica"},{"key":"746_CR29","doi-asserted-by":"crossref","unstructured":"Hartung, S., Hoos, H.H.: Programming by optimisation meets parameterised algorithmics: a case study for cluster editing. In: Proceedings of the 9th International Conference on Learning and Intelligent Optimization, LION 2015, Volume 8994 of LNCS, pp. 43\u201358. Springer (2015)","DOI":"10.1007\/978-3-319-19084-6_5"},{"key":"746_CR30","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"746_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972)"},{"key":"746_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Boston (2004)"},{"issue":"15","key":"746_CR33","doi-asserted-by":"publisher","first-page":"2259","DOI":"10.1016\/j.dam.2012.05.019","volume":"160","author":"C Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Uhlmann, J.: Cluster editing with locally bounded modifications. Discrete Appl. Math. 160(15), 2259\u20132270 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"9","key":"746_CR34","doi-asserted-by":"publisher","first-page":"2637","DOI":"10.1007\/s00453-017-0349-6","volume":"80","author":"R Krithika","year":"2018","unstructured":"Krithika, R., Sahu, A., Tale, P.: Dynamic parameterized problems. Algorithmica 80(9), 2637\u20132655 (2018)","journal-title":"Algorithmica"},{"key":"746_CR35","unstructured":"Luo, J., Molter, H., Nichterlein, A., Niedermeier, R.: Parameterized dynamic cluster editing. In: Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS \u201918, Volume 122 of LIPIcs, pp. 46:1\u201346:15 (2018)"},{"issue":"1","key":"746_CR36","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/s00453-009-9326-z","volume":"58","author":"D Marx","year":"2010","unstructured":"Marx, D., Schlotter, I.: Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica 58(1), 170\u2013187 (2010)","journal-title":"Algorithmica"},{"key":"746_CR37","doi-asserted-by":"crossref","unstructured":"Meil\u0103, M.: Comparing clusterings: an axiomatic view. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 577\u2013584. ACM (2005)","DOI":"10.1145\/1102351.1102424"},{"issue":"3","key":"746_CR38","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10994-011-5267-2","volume":"86","author":"M Meil\u0103","year":"2012","unstructured":"Meil\u0103, M.: Local equivalences of distances between clusterings\u2014a geometric perspective. Mach. Learn. 86(3), 369\u2013389 (2012)","journal-title":"Mach. Learn."},{"key":"746_CR39","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"2","key":"746_CR40","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/s00453-017-0274-8","volume":"80","author":"B Schieber","year":"2018","unstructured":"Schieber, B., Shachnai, H., Tamir, G., Tamir, T.: A theory and algorithms for combinatorial reoptimization. Algorithmica 80(2), 576\u2013607 (2018)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"746_CR41","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1\u20132), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"746_CR42","doi-asserted-by":"crossref","unstructured":"Tang, W., Lu, Z., Dhillon, I.S.: Clustering with multiple graphs. In: Proceedings of the Ninth IEEE International Conference on Data Mining, ICDM 2009, pp. 1016\u20131021 (2009)","DOI":"10.1109\/ICDM.2009.125"},{"key":"746_CR43","doi-asserted-by":"crossref","unstructured":"Tantipathananandh, C., Berger-Wolf, T.Y.: Finding communities in dynamic social networks. In: Proceedings of the IEEE 11th International Conference on Data Mining, ICDM 2011, pp. 1236\u20131241 (2011)","DOI":"10.1109\/ICDM.2011.67"},{"key":"746_CR44","doi-asserted-by":"crossref","unstructured":"Tantipathananandh, C., Berger-Wolf, T.Y., Kempe, D.: A framework for community identification in dynamic social networks. In: Proceedings of the 13th SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2007, pp. 717\u2013726. ACM (2007)","DOI":"10.1145\/1281192.1281269"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00746-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00746-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00746-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T12:15:42Z","timestamp":1667564142000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00746-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,25]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["746"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00746-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,25]]},"assertion":[{"value":"12 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}