{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:22:55Z","timestamp":1771485775558,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T00:00:00Z","timestamp":1735948800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T00:00:00Z","timestamp":1735948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1814613"],"award-info":[{"award-number":["1814613"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1907937"],"award-info":[{"award-number":["1907937"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1910149"],"award-info":[{"award-number":["1910149"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["451026932"],"award-info":[{"award-number":["451026932"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1907937"],"award-info":[{"award-number":["1907937"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,11]]},"DOI":"10.1007\/s10107-024-02179-9","type":"journal-article","created":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T04:10:38Z","timestamp":1735963838000},"page":"153-200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Polyhedral aspects of feedback vertex set and pseudoforest deletion set"],"prefix":"10.1007","volume":"214","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3421-7238","authenticated-orcid":false,"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[]},{"given":"Shubhang","family":"Kulkarni","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,4]]},"reference":[{"key":"2179_CR1","doi-asserted-by":"crossref","unstructured":"Bafna, V., Berman, P. and Fujito, T.: Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In: Algorithms and Computations, pp. 142\u2013151 (1995)","DOI":"10.1007\/BFb0015417"},{"key":"2179_CR2","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83, 167\u2013188 (1996)","journal-title":"Artif. Intell."},{"key":"2179_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Ono, H., Otachi, Y.: A faster parameterized algorithm for Pseudoforest Deletion. Discrete Appl. Math. 236, 42-56 (2018)","DOI":"10.1016\/j.dam.2017.10.018"},{"issue":"2","key":"2179_CR4","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1002\/net.21825","volume":"72","author":"A Buchanan","year":"2018","unstructured":"Buchanan, A., Wang, Y., Butenko, S.: Algorithms for node-weighted Stediner tree and maximum-weight connected subgraph. Networks 72(2), 238\u2013248 (2018)","journal-title":"Networks"},{"issue":"4","key":"2179_CR5","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2179_CR6","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"FA Chudak","year":"1998","unstructured":"Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4), 111\u2013118 (1998)","journal-title":"Oper. Res. Lett."},{"key":"2179_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Approximation Algorithms for Combinatorial Optimization, pp. 84\u201395 (2000)","DOI":"10.1007\/3-540-44436-X_10"},{"key":"2179_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Madan, V.: Constant factor approximation for subset feedback set problems via a new LP relaxation. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 808\u2013820. SODA (2016)","DOI":"10.1137\/1.9781611974331.ch58"},{"key":"2179_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 439\u2013485 (2005)","DOI":"10.4007\/annals.2005.162.439"},{"issue":"2","key":"2179_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/S0895480195291874","volume":"13","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Schieber, B., Zosin, L.: Approximating minimum subset feedback sets in undirected graphs with applications. SIAM J. Discrete Math. 13(2), 255\u2013267 (2000)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"2179_CR11","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"key":"2179_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","volume":"9","author":"P Erd\u00f6s","year":"1962","unstructured":"Erd\u00f6s, P., P\u00f3sa, L.: On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen 9, 3\u201312 (1962)","journal-title":"Publ. Math. Debrecen"},{"issue":"1","key":"2179_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1006\/jagm.1998.0995","volume":"31","author":"T Fujito","year":"1999","unstructured":"Fujito, T.: Approximating node-deletion problems for matroidal properties. J. Algorithms 31(1), 211\u2013227 (1999)","journal-title":"J. Algorithms"},{"key":"2179_CR14","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Elsevier (2005)"},{"issue":"3","key":"2179_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-$$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"2179_CR16","first-page":"08","volume":"806","author":"M Lin","year":"2019","unstructured":"Lin, M., Feng, Q., Bin, F., Wang, J.: An approximation algorithm for the $$\\ell $$-pseudoforest deletion problem. Theor. Comput. Sci. 806, 08 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"2179_CR17","unstructured":"Monien, B., Schulz, R.: Four approximation algorithms for the feedback vertex set problem. In WG, pp. 315\u2013326 (1981)"},{"issue":"2","key":"2179_CR18","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/16M1100794","volume":"32","author":"G Philip","year":"2018","unstructured":"Philip, G., Rai, A., Saurabh, S.: Generalized pseudoforest deletion: algorithms and uniform kernel. SIAM J. Discrete Math. 32(2), 882\u2013901 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"2179_CR19","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall (2000)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02179-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02179-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02179-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:37:23Z","timestamp":1764574643000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02179-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,4]]},"references-count":19,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2179"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02179-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,4]]},"assertion":[{"value":"25 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}