{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:22Z","timestamp":1787337622345,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set (or subset-fvs, in short). The input in this problem consists of an undirected graph G=(V,E) with vertex weights c(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset-fvs with respect to S if it intersects every interesting cycle. The goal is to find a minimum weight subset-fvs. The best previous algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset-fvs problem generalizes two NP-complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multicommodity flow, which we call relaxed multicommodity flow. Relaxed multicommodity flow is a hybrid of multicommodity flow and multiterminal flow.<\/jats:p>","DOI":"10.1137\/s0097539798340047","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1231-1252","source":"Crossref","is-referenced-by-count":45,"title":["An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem"],"prefix":"10.1137","volume":"30","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid","family":"Zosin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"R. K. Ahuja, T. L. Magnanati, and J. B. Orlin,\n                      Network Flows\n                      , Prentice Hall, Englewood Cliffs, New Jersey, 1993."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00004-6"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. Calinescu, H. Karloff, and Y. Rabani,\n                      An improved approximation algorithm for multi\u2010way cut\n                      , in Proceedings of the 30th ACM Symposium on Theory of Computing, Dallas, TX, 1998, pp. 48\u201352.","DOI":"10.1145\/276698.276711"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan, Approximating minimum feedback sets and multi\u2010cuts in directed graphs, Lecture Notes in Comput. Sci., Vol. 920, Springer, Berlin, 1995, 14\u201328CMP1367968","DOI":"10.1007\/3-540-59408-6_38"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"G. Even, J. Naor, S. Rao, and B. Schieber,\n                      Divide\u2010and\u2010conquer approximation algorithms via spreading metrics\n                      , in Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1995, pp. 62\u201371; J. ACM, to appear.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195291874"},{"key":"R9","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , W. H. Freeman, San Francisco, California, 1979."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis,\n                      Multiway cuts in directed and node weighted graphs\n                      , in Proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci. 820, Springer, New York, 1994, pp. 487\u2013498.","DOI":"10.1007\/3-540-58201-0_92"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90079-X"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Meena Mahajan, P. Subramanya, V. Vinay, A combinatorial algorithm for Pfaffians, Lecture Notes in Comput. Sci., Vol. 1627, Springer, Berlin, 1999, 134\u20131432000i:05002","DOI":"10.1007\/3-540-48686-0_13"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. R. Karger, P. N. Klein, C. Stein, M. Thorup, and N. E. Young,\n                      Rounding algorithms for a geometric embedding of minimum multiway cut\n                      , in Proceedings of the 31st ACM Symposium on Theory of Computing, Atlanta, GA, 1999, pp. 668\u2013678.","DOI":"10.1145\/301250.301430"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, NewYork, 1972, pp. 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0833"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Naor and L. Zosin,\n                      A 2\u2010approximation algorithm for the directed multiway cut problem\n                      , in Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1997, pp. 548\u2013553.","DOI":"10.1109\/SFCS.1997.646144"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539798340047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:27Z","timestamp":1787336487000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539798340047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539798340047"],"URL":"https:\/\/doi.org\/10.1137\/s0097539798340047","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}