{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T05:59:17Z","timestamp":1772171957876,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:00:00Z","timestamp":1641513600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["615640-ForEFront"],"award-info":[{"award-number":["615640-ForEFront"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","award":["T008720F-35293308-BD-OCP."],"award-info":[{"award-number":["T008720F-35293308-BD-OCP."]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10107-021-01744-w","type":"journal-article","created":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T00:03:47Z","timestamp":1641513827000},"page":"1069-1091","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A tight approximation algorithm for the cluster vertex deletion problem"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6805-6903","authenticated-orcid":false,"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[]},{"given":"Matthew","family":"Drescher","sequence":"additional","affiliation":[]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[]},{"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,7]]},"reference":[{"issue":"6794","key":"1744_CR1","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/35019019","volume":"406","author":"R Albert","year":"2000","unstructured":"Albert, R., Jeong, H., Barab\u00e1si, A.L.: Error and attack tolerance of complex networks. Nature 406(6794), 378\u2013382 (2000)","journal-title":"Nature"},{"key":"1744_CR2","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 4th edn. Wiley, New York (2016)","edition":"4"},{"key":"1744_CR3","unstructured":"Aprile, M.: Extended formulations for matroid polytopes through randomized protocols. arXiv preprintarXiv:2106.12453, (2021)"},{"issue":"1","key":"1744_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1111\/itor.12562","volume":"26","author":"M Aprile","year":"2019","unstructured":"Aprile, M., Castro, N., Ferreira, G., Piccini, J., Robledo, F., Romero, P.: Graph fragmentation problem: analysis and synthesis. Int. Trans. Oper. Res. 26(1), 41\u201353 (2019)","journal-title":"Int. Trans. Oper. Res."},{"key":"1744_CR5","unstructured":"Aprile, M., Castro, N., Robledo, F., Romero, P.: Analysis and complexity of node-immunization under natural disasters. In: DRCN 2017-Design of Reliable Communication Networks; 13th International Conference, pages 1\u20138. VDE, (2017)"},{"key":"1744_CR6","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A simple 7\/3-approximation algorithm for feedback vertex set in tournaments. arXiv preprintarXiv:2008.08779, (2020)"},{"key":"1744_CR7","doi-asserted-by":"crossref","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. In: International Conference on Integer Programming and Combinatorial Optimization, pages 340\u2013353. Springer, (2021)","DOI":"10.1007\/978-3-030-73879-2_24"},{"issue":"1","key":"1744_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s10107-020-01535-9","volume":"183","author":"M Aprile","year":"2020","unstructured":"Aprile, M., Faenza, Y.: Extended formulations from communication protocols in output-efficient time. Math. Programm. 183(1), 41\u201359 (2020)","journal-title":"Math. Programm."},{"key":"1744_CR9","doi-asserted-by":"crossref","unstructured":"Aprile, M.\u00a0F., Faenza, Y., Fiorini, S., Huynh, T., Macchia, M.: Extension complexity of stable set polytopes of bipartite graphs. Lecture Notes in Computer Science book series (LNCS), 10520(CONF):75\u201387, (2017)","DOI":"10.1007\/978-3-319-68705-6_6"},{"issue":"1","key":"1744_CR10","first-page":"147","volume":"44","author":"A Bazzi","year":"2019","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor $$2 - \\epsilon $$. Math. Oper. Res. 44(1), 147\u2013172 (2019)","journal-title":"Math. Oper. Res."},{"key":"1744_CR11","doi-asserted-by":"crossref","unstructured":"Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation, pp. 1\u201329. Springer, (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"issue":"2","key":"1744_CR12","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)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20132","key":"1744_CR13","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s10107-018-1316-y","volume":"172","author":"G Braun","year":"2018","unstructured":"Braun, G., Pokutta, S., Roy, A.: Strong reductions for extended formulations. Math. Program. 172(1\u20132), 591\u2013620 (2018)","journal-title":"Math. Program."},{"key":"1744_CR14","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceedings of STOC 2015, pp. 107\u2013116, New York, NY, USA. ACM (2015)","DOI":"10.1145\/2746539.2746550"},{"issue":"6","key":"1744_CR15","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1137\/S0097539798338163","volume":"30","author":"M-C Cai","year":"2001","unstructured":"Cai, M.-C., Deng, X., Zang, W.: An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30(6), 1993\u20132007 (2001)","journal-title":"SIAM J. Comput."},{"key":"1744_CR16","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)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1744_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2811255","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. J. ACM (JACM) 63(4), 1\u201322 (2016)","journal-title":"J. ACM (JACM)"},{"key":"1744_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer Programming, vol. 271. Springer, Berlin (2014)"},{"key":"1744_CR19","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Joret, G., Schaudt, O.: Improved approximation algorithms for hitting 3-vertex paths. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 238\u2013249. Springer, (2016)","DOI":"10.1007\/978-3-319-33461-5_20"},{"issue":"1\u20132, Ser. A","key":"1744_CR20","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s10107-019-01395-y","volume":"182","author":"S Fiorini","year":"2020","unstructured":"Fiorini, S., Joret, G., Schaudt, O.: Improved approximation algorithms for hitting 3-vertex paths. Math. Program. 182(1\u20132, Ser. A), 355\u2013367 (2020)","journal-title":"Math. Program."},{"key":"1744_CR21","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. J. ACM, 66(2):Art. 8, 23, (2019)","DOI":"10.1145\/3284176"},{"issue":"1","key":"1744_CR22","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3293466","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Le, T., Lokshtanov, D., Saurabh, S., Thomass\u00e9, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. ACM Trans. Algorithms 15(1), 13:1-13:44 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1744_CR23","first-page":"422","volume":"36","author":"A Freund","year":"2005","unstructured":"Freund, A., Bar-Yehuda, R., Bendel, K.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36, 422\u2013463 (2005)","journal-title":"ACM Comput. Surv."},{"key":"1744_CR24","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2021.02.040","volume":"297","author":"S Hosseinian","year":"2021","unstructured":"Hosseinian, S., Butenko, S.: Polyhedral properties of the induced cluster subgraphs. Discrete Appl. Math. 297, 80\u201396 (2021)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1744_CR25","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)","journal-title":"Theory Comput. Syst."},{"issue":"12","key":"1744_CR26","doi-asserted-by":"publisher","first-page":"3458","DOI":"10.1016\/j.cnsns.2013.04.030","volume":"18","author":"E Jahanpour","year":"2013","unstructured":"Jahanpour, E., Chen, X.: Analysis of complex network performance and heuristic node removal strategies. Commun. Nonlinear Sci. Numer. Simul. 18(12), 3458\u20133468 (2013)","journal-title":"Commun. Nonlinear Sci. Numer. Simul."},{"key":"1744_CR27","doi-asserted-by":"crossref","unstructured":"Kothari, P.K., Meka, R., Raghavendra, P.: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In: Hatami, H, McKenzie, P., King, V. (eds), Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 590\u2013603. ACM, (2017)","DOI":"10.1145\/3055399.3055438"},{"issue":"3","key":"1744_CR28","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"key":"1744_CR29","unstructured":"Lokshtanov, D.: Personal communication"},{"key":"1744_CR30","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Mukherjee, J., Panolan, F., Philip, G., Saurabh, S.: $$2$$-approximating feedback vertex set in tournaments. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1010\u20131018. SIAM, (2020)","DOI":"10.1137\/1.9781611975994.61"},{"key":"1744_CR31","unstructured":"Mnich, M., Williams, V.V., V\u00e9gh, L.A.: A 7\/3-approximation for feedback vertex sets in tournaments. In: Sankowski, P., Zaroliagis, C.D. (eds), 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume\u00a057 of LIPIcs, pages 67:1\u201367:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2016)"},{"key":"1744_CR32","unstructured":"Rothvo\u00df, T.: The Lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP, pp. 1\u201325, (2013)"},{"key":"1744_CR33","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"issue":"3","key":"1744_CR34","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"1744_CR35","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221\u2013232 (1985)","journal-title":"Discrete Math."},{"issue":"3","key":"1744_CR36","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"1744_CR37","unstructured":"Tiwary, H.\u00a0R., Kouteck\u1ef3, M., Kolman, P.: Extension complexity, MSO logic, and treewidth. Discrete Math. Theor. Computer Sci., 22, (2020)"},{"key":"1744_CR38","doi-asserted-by":"crossref","unstructured":"Tsur, D.: Faster parameterized algorithm for cluster vertex deletion. CoRR, arXiv:1901.07609, (2019)","DOI":"10.1016\/j.ipl.2019.03.009"},{"key":"1744_CR39","unstructured":"V\u00e9gh, L.A.: Personal communication"},{"key":"1744_CR40","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/j.dam.2016.11.007","volume":"219","author":"J You","year":"2017","unstructured":"You, J., Wang, J., Cao, Y.: Approximate association via dissociation. Discret. Appl. Math. 219, 202\u2013209 (2017)","journal-title":"Discret. Appl. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01744-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01744-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01744-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:16:46Z","timestamp":1675703806000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01744-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,7]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1744"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01744-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,7]]},"assertion":[{"value":"26 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}