{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:00Z","timestamp":1761621060672,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            We investigate the computational complexity of a general \u201ccompression task\u201d centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of the following task: given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, find a smaller\n            <jats:italic>disjoint<\/jats:italic>\n            solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that a few cases are polynomial-time solvable, and the others are NP-hard. The considered class of vertex deletion problems includes Vertex Cover (where the compression task is polynomial time) and Undirected Feedback Vertex Set (where the compression task is NP-complete).\n          <\/jats:p>","DOI":"10.1145\/1944857.1944860","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems"],"prefix":"10.1145","volume":"2","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[{"name":"Charles Darwin University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[{"name":"Universit\u00e4t des Saarlandes"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hannes","family":"Moser","sequence":"additional","affiliation":[{"name":"Friedrich-Schiller-Universit\u00e4t Jena"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"TU Berlin"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aarts E. and Lenstra J. K. 1997. Local Search in Combinatorial Optimization. Wiley. Aarts E. and Lenstra J. K. 1997. Local Search in Combinatorial Optimization . Wiley."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902)","volume":"2286","author":"Abello J.","unstructured":"Abello , J. , Resende , M. G. C. , and Sudarsky , S . 2002. Massive quasi-clique detection . In Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902) . Lecture Notes in Computer Science , vol. 2286 . Springer, 598--612. Abello, J., Resende, M. G. C., and Sudarsky, S. 2002. Massive quasi-clique detection. In Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN \u201902). Lecture Notes in Computer Science, vol. 2286. Springer, 598--612."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908)","volume":"4910","author":"B\u00f6ckenhauer H.-J.","unstructured":"B\u00f6ckenhauer , H.-J. , Hromkovi\u010d , J. , M\u00f6mke , T. , and Widmayer , P . 2008. On the hardness of reoptimization . In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908) . Lecture Notes in Computer Science , vol. 4910 . Springer, 50--65. B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., and Widmayer, P. 2008. On the hardness of reoptimization. In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908). Lecture Notes in Computer Science, vol. 4910. Springer, 50--65."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.05.002"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1345-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_2_1_9_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . Freeman."},{"volume-title":"Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing. 389--394","author":"Greenwell D. L.","key":"e_1_2_1_10_1","unstructured":"Greenwell , D. L. , Hemminger , R. L. , and Klerlein , J. B . 1973. Forbidden subgraphs . In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing. 389--394 . Greenwell, D. L., Hemminger, R. L., and Klerlein, J. B. 1973. Forbidden subgraphs. In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing. 389--394."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.02.001"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9150-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00414-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1611"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201907)","volume":"4769","author":"Marx D.","unstructured":"Marx , D. and Schlotter , I . 2007. Obtaining a planar graph by vertex deletion . In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201907) . Lecture Notes in Computer Science , vol. 4769 . Springer, 292--303. Marx, D. and Schlotter, I. 2007. Obtaining a planar graph by vertex deletion. In Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201907). Lecture Notes in Computer Science, vol. 4769. Springer, 292--303."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_22"},{"volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier R.","key":"e_1_2_1_21_1","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.02.029"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944857.1944860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1944857.1944860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:31Z","timestamp":1750244371000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1944857.1944860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1944857.1944860"],"URL":"https:\/\/doi.org\/10.1145\/1944857.1944860","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}