{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:00Z","timestamp":1750309140114,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T00:00:00Z","timestamp":1702166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["714704"],"award-info":[{"award-number":["714704"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V,E<\/jats:italic>\n            ) and an integer\n            <jats:italic>k<\/jats:italic>\n            , the\n            <jats:sc>Cluster Editing<\/jats:sc>\n            problem asks whether we can transform\u00a0\n            <jats:italic>G<\/jats:italic>\n            into a union of vertex-disjoint cliques by at most\n            <jats:italic>k<\/jats:italic>\n            modifications (edge deletions or insertions). In this paper, we study the following variant of\n            <jats:sc>Cluster Editing<\/jats:sc>\n            . We are given a graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V,E<\/jats:italic>\n            ), a packing\u00a0\u210b of modification-disjoint induced\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            s (no pair of\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            s in \u210b share an edge or non-edge) and an integer\u00a0\u2113. The task is to decide whether\n            <jats:italic>G<\/jats:italic>\n            can be transformed into a union of vertex-disjoint cliques by at most \u2113 +|\u210b| modifications (edge deletions or insertions). We show that this problem is NP-hard even when \u2113 = 0 (in which case the problem asks to turn\n            <jats:italic>G<\/jats:italic>\n            into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of \u210b) and when each vertex is in at most 23\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer\n            <jats:italic>c<\/jats:italic>\n            such that the problem remains tractable when restricting to packings such that each vertex is in at most\n            <jats:italic>c<\/jats:italic>\n            packed\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            s. Here packed\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            s are those belonging to the packing\u00a0\u210b. Van Bevern et\u00a0al. showed that the case\n            <jats:italic>c<\/jats:italic>\n            = 1 is fixed-parameter tractable with respect to \u2113 and we show that the case\n            <jats:italic>c<\/jats:italic>\n            = 2 is solvable in |\n            <jats:italic>V<\/jats:italic>\n            |\n            <jats:sup>\n              2\u2113 +\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            \u00a0time.\n          <\/jats:p>","DOI":"10.1145\/3626526","type":"journal-article","created":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T15:27:19Z","timestamp":1697038039000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cluster Editing Parameterized above Modification-disjoint\n            <i>P<\/i>\n            <sub>3<\/sub>\n            -packings"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8079-6405","authenticated-orcid":false,"given":"Shaohua","family":"Li","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7394-3147","authenticated-orcid":false,"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[{"name":"University of Warsaw, Poland and TU Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"issue":"3","key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/s00222-005-0465-9","article-title":"Quadratic forms on graphs","volume":"163","author":"Alon Noga","year":"2006","unstructured":"Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. 2006. Quadratic forms on graphs. Inventiones Mathematicae 163, 3 (2006), 499\u2013522.","journal-title":"Inventiones Mathematicae"},{"key":"e_1_3_2_5_2","article-title":"On non-approximability for quadratic programs","volume":"058","author":"Arora Sanjeev","year":"2005","unstructured":"Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. 2005. On non-approximability for quadratic programs. Electronic Colloquium on Computational Complexity (ECCC) 058 (2005). http:\/\/eccc.hpi-web.de\/eccc-reports\/2005\/TR05-058\/index.html","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1089\/106652799318274"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.04.005"},{"key":"e_1_3_2_9_2","first-page":"33","volume-title":"Proceedings of the 9th Conference on Computability in Europe (CiE 2013) (Lecture Notes in Computer Science)","volume":"7921","author":"B\u00f6cker Sebastian","year":"2013","unstructured":"Sebastian B\u00f6cker and Jan Baumbach. 2013. Cluster editing. In Proceedings of the 9th Conference on Computability in Europe (CiE 2013) (Lecture Notes in Computer Science), Paola Bonizzoni, Vasco Brattka, and Benedikt L\u00f6we (Eds.), Vol. 7921. Springer, 33\u201344. DOI:10.1007\/978-3-642-39053-1_5"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.006"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9339-7"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.003"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.12.016"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/140961808"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9595-1"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.04.001"},{"key":"e_1_3_2_18_2","article-title":"A survey of parameterized algorithms and the complexity of edge modification","author":"Crespelle Christophe","year":"2020","unstructured":"Christophe Crespelle, P\u00e5l Gr\u00f8n\u00e5s Drange, Fedor V. Fomin, and Petr A. Golovach. 2020. A survey of parameterized algorithms and the complexity of edge modification. arXiv:2001.06867 [cs] (2020). arxiv:cs\/2001.06867","journal-title":"arXiv:2001.06867 [cs]"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9130-1"},{"key":"e_1_3_2_21_2","first-page":"276","volume-title":"Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC 2006) (Lecture Notes in Computer Science)","volume":"4169","author":"Fellows Michael R.","year":"2006","unstructured":"Michael R. Fellows. 2006. The lost continent of polynomial time: Preprocessing and kernelization. In Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC 2006) (Lecture Notes in Computer Science), Hans L. Bodlaender and Michael A. Langston (Eds.), Vol. 4169. Springer, 276\u2013277. DOI:10.1007\/11847250_25"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.09.006"},{"key":"e_1_3_2_23_2","first-page":"312","volume-title":"Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007) (Lecture Notes in Computer Science)","volume":"4639","author":"Fellows Michael R.","year":"2007","unstructured":"Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Peter Shaw. 2007. Efficient parameterized preprocessing for cluster editing. In Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007) (Lecture Notes in Computer Science), Erzs\u00e9bet Csuhaj-Varj\u00fa and Zolt\u00e1n \u00c9sik (Eds.), Vol. 4639. Springer, 312\u2013321. DOI:10.1007\/978-3-540-74240-1_27"},{"key":"e_1_3_2_24_2","article-title":"Subexponential fixed-parameter tractability of cluster editing","author":"Fomin Fedor V.","year":"2013","unstructured":"Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Yngve Villanger. 2013. Subexponential fixed-parameter tractability of cluster editing. arXiv:1112.4419 [cs] (2013). arxiv:cs\/1112.4419","journal-title":"arXiv:1112.4419 [cs]"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.04.015"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.14279\/depositonce-7123"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1137\/1.9781611974331.ch80","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)","author":"Garg Shivam","year":"2016","unstructured":"Shivam Garg and Geevarghese Philip. 2016. Raising the bar for vertex cover: Fixed-parameter tractability above A higher guarantee. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Robert Krauthgamer (Ed.). SIAM, 1152\u20131166. DOI:10.1137\/1.9781611974331.ch80"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1090-5"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1178-y"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.10.021"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9487-4"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/090767285"},{"key":"e_1_3_2_33_2","first-page":"68:1\u201368:14","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"80","author":"Iwata Yoichi","year":"2017","unstructured":"Yoichi Iwata. 2017. Linear-time kernelization for feedback vertex set. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.), Vol. 80. Schloss Dagstuhl\u2013 Leibniz-Zentrum fuer Informatik, 68:1\u201368:14. DOI:10.4230\/LIPIcs.ICALP.2017.68"},{"key":"e_1_3_2_34_2","unstructured":"Bart M. P. Jansen Christian Schulz and Hisao Tamaki. 2019. NII Shonan Meeting Report no. 144 Parameterized Graph Algorithms and Data Reduction. (2019). https:\/\/shonan.nii.ac.jp\/docs\/No.144.pdf"},{"key":"e_1_3_2_35_2","first-page":"12:1\u201312:12","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms (SEA 2018) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"103","author":"Kiljan Krzysztof","year":"2018","unstructured":"Krzysztof Kiljan and Marcin Pilipczuk. 2018. Experimental evaluation of parameterized algorithms for feedback vertex set. In Proceedings of the 17th International Symposium on Experimental Algorithms (SEA 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), Gianlorenzo D\u2019Angelo (Ed.), Vol. 103. Schloss Dagstuhl\u2013 Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 12:1\u201312:12. DOI:10.4230\/LIPIcs.SEA.2018.12"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.019"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104585"},{"key":"e_1_3_2_38_2","first-page":"49:1\u201349:16","volume-title":"Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"187","author":"Li Shaohua","year":"2021","unstructured":"Shaohua Li, Marcin Pilipczuk, and Manuel Sorge. 2021. Cluster editing parameterized above modification-disjoint \\(P_3\\) -packings. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (Leibniz International Proceedings in Informatics (LIPIcs)), Markus Bl\u00e4ser and Benjamin Monmege (Eds.), Vol. 187. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 49:1\u201349:16. DOI:10.4230\/LIPIcs.STACS.2021.49"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-436"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9032-7"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.007"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9746-5"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth0610-419"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:16Z","timestamp":1750287016000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,10]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3626526"],"URL":"https:\/\/doi.org\/10.1145\/3626526","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,12,10]]},"assertion":[{"value":"2022-09-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}