{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T11:30:54Z","timestamp":1769772654840,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T00:00:00Z","timestamp":1708646400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T00:00:00Z","timestamp":1708646400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012688","name":"Universit\u00e4t Rostock","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012688","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The well-known Cluster Vertex Deletion problem (<jats:sc>cluster-vd<\/jats:sc>) asks for a given graph <jats:italic>G<\/jats:italic> and an integer <jats:italic>k<\/jats:italic> whether it is possible to delete a set <jats:italic>S<\/jats:italic> of at most <jats:italic>k<\/jats:italic> vertices of <jats:italic>G<\/jats:italic> such that the resulting graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G-S$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>S<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs <jats:italic>H<\/jats:italic> for which <jats:sc>cluster-vd<\/jats:sc> on <jats:italic>H<\/jats:italic>-free graphs is polynomially solvable and for which it is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete. Moreover, in the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-completeness cases, <jats:sc>cluster-vd<\/jats:sc> cannot be solved in sub-exponential time in the vertex number of the <jats:italic>H<\/jats:italic>-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of <jats:sc>cluster-vd<\/jats:sc>, the Connected Cluster Vertex Deletion problem (<jats:sc>connected cluster-vd<\/jats:sc>), in which the set <jats:italic>S<\/jats:italic> has to induce a connected subgraph of <jats:italic>G<\/jats:italic>. It turns out that <jats:sc>connected cluster-vd<\/jats:sc> admits the same complexity dichotomy for <jats:italic>H<\/jats:italic>-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on <jats:italic>H<\/jats:italic>-free graphs.<\/jats:p>","DOI":"10.1007\/s00224-024-10161-3","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T12:02:51Z","timestamp":1708689771000},"page":"250-270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs"],"prefix":"10.1007","volume":"68","author":[{"given":"Hoang-Oanh","family":"Le","sequence":"first","affiliation":[]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,23]]},"reference":[{"issue":"2","key":"10161_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1007\/s10107-021-01744-w","volume":"197","author":"M Aprile","year":"2023","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. Math. Program. 197(2), 1069\u20131091 (2023). https:\/\/doi.org\/10.1007\/s10107-021-01744-w","journal-title":"Math. Program."},{"issue":"2","key":"10161_CR2","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A Fast Branching Algorithm for Cluster Vertex Deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016). https:\/\/doi.org\/10.1007\/s00224-015-9631-7","journal-title":"Theory Comput. Syst."},{"key":"10161_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2018.05.039","volume":"745","author":"Y Cao","year":"2018","unstructured":"Cao, Y., Ke, Y., Otachi, Y., You, J.: Vertex deletion problems on chordal graphs. Theor. Comput. Sci. 745, 75\u201386 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.05.039","journal-title":"Theor. Comput. Sci."},{"key":"10161_CR4","doi-asserted-by":"publisher","unstructured":"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.) Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, Proceedings. Lecture Notes in Computer Science, vol. 12757, pp. 152\u2013164. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-79987-8_11","DOI":"10.1007\/978-3-030-79987-8_11"},{"issue":"2","key":"10161_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P.D., Vuskovic, K.: Recognizing Berge Graphs. Combinatorica 25(2), 143\u2013186 (2005). https:\/\/doi.org\/10.1007\/s00493-005-0012-8","journal-title":"Combinatorica"},{"issue":"3","key":"10161_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981). https:\/\/doi.org\/10.1016\/0166-218X(81)90013-5","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"10161_CR7","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A Linear Recognition Algorithm for Cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985). https:\/\/doi.org\/10.1137\/0214065","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10161_CR8","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-Rewriting Hypergraph Grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90004-G","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10161_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"key":"10161_CR10","doi-asserted-by":"publisher","unstructured":"Gartland, P., Lokshtanov, D.: Independent Set on $$P_{k}$$-Free Graphs in Quasi-Polynomial Time. In: Irani S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, pp. 613\u2013624. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00063","DOI":"10.1109\/FOCS46700.2020.00063"},{"issue":"4","key":"10161_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A Survey on the Computational Complexity of Coloring Graphs with Forbidden subgraphs. J. Graph Theory 84(4), 331\u2013363 (2017). https:\/\/doi.org\/10.1002\/jgt.22028","journal-title":"J. Graph Theory"},{"key":"10161_CR12","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1988). https:\/\/doi.org\/10.1007\/978-3-642-97881-4","DOI":"10.1007\/978-3-642-97881-4"},{"issue":"1","key":"10161_CR13","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik, A., Klimosov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time Algorithm for Maximum Weight Independent Set on $$P_{6}$$-free Graphs. ACM Trans. Algorithms 18(1), 4:1-4:57 (2022). https:\/\/doi.org\/10.1145\/3414473","journal-title":"ACM Trans. Algorithms"},{"key":"10161_CR14","doi-asserted-by":"publisher","unstructured":"Hsieh, S.-Y., Le, H.-O., Le, V.B., Peng, S.-L.: On the $$d$$-Claw Vertex Deletion Problem. Algorithmica (2023). https:\/\/doi.org\/10.1007\/s00453-023-01144-w","DOI":"10.1007\/s00453-023-01144-w"},{"issue":"1","key":"10161_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-Parameter Algorithms for Cluster Vertex Deletion. Theory Comput. Syst. 47(1), 196\u2013217 (2010). https:\/\/doi.org\/10.1007\/s00224-008-9150-x","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"10161_CR16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10161_CR17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"10161_CR18","unstructured":"Johnson, D.S., Szegedy, M.: What are the Least Tractable Instances of Max Independent Set? In: Tarjan, R.E., Warnow, T.J. (eds) Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, USA, pp. 927\u2013928. ACM\/SIAM, (1999). http:\/\/dl.acm.org\/citation.cfm?id=314500.315093"},{"issue":"1","key":"10161_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00453-019-00601-9","volume":"82","author":"M Johnson","year":"2020","unstructured":"Johnson, M., Paesani, G., Paulusma, D.: Connected Vertex Cover for ($$sP_{1} + P_{5}$$)-Free Graphs. Algorithmica 82(1), 20\u201340 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00601-9","journal-title":"Algorithmica"},{"key":"10161_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2012.02.036","volume":"438","author":"M Kamin\u015bki","year":"2012","unstructured":"Kamin\u015bki, M.: Max-Cut and containment relations in graphs. Theor. Comput. Sci. 438, 89\u201395 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.036","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10161_CR21","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/3186589","volume":"10","author":"C Komusiewicz","year":"2018","unstructured":"Komusiewicz, C.: Tight Running Time Lower Bounds for Vertex Deletion Problems. ACM Trans. Comput. Theory 10(2), 6:1-6:18 (2018). https:\/\/doi.org\/10.1145\/3186589","journal-title":"ACM Trans. Comput. Theory"},{"key":"10161_CR22","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1515\/dma.1992.2.2.191","volume":"2","author":"DV Korobitsin","year":"1992","unstructured":"Korobitsin, D.V.: On the complexity of domination number determination in monogenic classes of graphs. Discrete Math. Appl. 2, 191\u2013200 (1992). https:\/\/doi.org\/10.1515\/dma.1992.2.2.191","journal-title":"Discrete Math. Appl."},{"key":"10161_CR23","doi-asserted-by":"publisher","unstructured":"Kr\u00e1l, D., Kratochv\u00edl, J., Tuza, Z., Woeginger, G.J.: Complexity of Coloring Graphs without Forbidden Induced Subgraphs. In: Brandst\u00e4dt A., Le, V.B. (eds.) Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, Proceedings. Lecture Notes in Computer Science, vol. 2204, pp. 254\u2013262. Springer (2001). https:\/\/doi.org\/10.1007\/3-540-45477-2_23","DOI":"10.1007\/3-540-45477-2_23"},{"key":"10161_CR24","doi-asserted-by":"publisher","unstructured":"Le, H.-O., Le, V.B.: Complexity of the Cluster Vertex Deletion Problem on $$H$$-Free Graphs. In: Szeider S., Ganian R., Silva A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), vol. 241 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 68:1\u201368:10, Dagstuhl, Germany (2022). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2022.68","DOI":"10.4230\/LIPIcs.MFCS.2022.68"},{"issue":"2","key":"10161_CR25","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The Node-Deletion Problem for Hereditary Properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","journal-title":"J. Comput. Syst. Sci."},{"key":"10161_CR26","unstructured":"Moret, B.M.E.: Theory of Computation. Addison-Wesley-Longman. (1998)"},{"key":"10161_CR27","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2017.06.012","volume":"692","author":"A Munaro","year":"2017","unstructured":"Munaro, A.: Boundary classes for graph problems involving non-local properties. Theor. Comput. Sci. 692, 46\u201371 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.06.012","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10161_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0166-218X(92)90041-8","volume":"35","author":"OJ Murphy","year":"1992","unstructured":"Murphy, O.J.: Computing independent sets in graphs with large girth. Discret. Appl. Math. 35(2), 167\u2013170 (1992). https:\/\/doi.org\/10.1016\/0166-218X(92)90041-8","journal-title":"Discret. Appl. Math."},{"key":"10161_CR29","doi-asserted-by":"publisher","first-page":"104812","DOI":"10.1016\/j.ic.2021.104812","volume":"281","author":"I Sau","year":"2021","unstructured":"Sau, I., dos Santos Souza, U.: Hitting forbidden induced subgraphs on bounded treewidth graphs. Inf. Comput. 281, 104812 (2021). https:\/\/doi.org\/10.1016\/j.ic.2021.104812","journal-title":"Inf. Comput."},{"issue":"1","key":"10161_CR30","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85\u201389 (1984). https:\/\/doi.org\/10.1016\/0166-218X(84)90081-7","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"10161_CR31","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00224-020-10005-w","volume":"65","author":"D Tsur","year":"2021","unstructured":"Tsur, D.: Faster Parameterized Algorithm for Cluster Vertex Deletion. Theory Comput. Syst. 65(2), 323\u2013343 (2021). https:\/\/doi.org\/10.1007\/s00224-020-10005-w","journal-title":"Theory Comput. Syst."},{"key":"10161_CR32","doi-asserted-by":"publisher","unstructured":"Yannakakis, M.: Node- and Edge-Deletion NP-Complete Problems. In: Lipton R.J., Burkhard W.A., Savitch W.J., Friedman E.P., Aho A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, pp. 253\u2013264. ACM (1978). https:\/\/doi.org\/10.1145\/800133.804355","DOI":"10.1145\/800133.804355"},{"issue":"2","key":"10161_CR33","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-Deletion Problems on Bipartite Graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981). https:\/\/doi.org\/10.1137\/0210022","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10161-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10161-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10161-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T04:02:38Z","timestamp":1712289758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10161-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,23]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10161"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10161-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,23]]},"assertion":[{"value":"8 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}