{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:01:25Z","timestamp":1787385685156,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>Let G=(V,E) be a weighted undirected graph where all weights are at least one. We consider the following generalization of feedback set problems. Let $S \\subset V$ be a subset of the vertices. A cycle is called interesting if it intersects the set S. A subset feedback edge (vertex) set is a subset of the edges (vertices) that intersects all interesting cycles. In minimum subset feedback problems the goal is to find such sets of minimum weight. This problem has a variety of applications, among them genetic linkage analysis and circuit testing. The case in which S consists of a single vertex is equivalent to the multiway cut problem, in which the goal is to separate a given set of terminals. Hence, the subset feedback problem is NP-complete and also generalizes the multiway cut problem. We provide a polynomial time algorithm for approximating the subset feedback edge set problem that achieves an approximation factor of two. This implies a $\\Delta$-approximation algorithm for the subset feedback vertex set problem, where $\\Delta$ is the maximum degree in G. We also consider the multicut problem and show how to achieve an $O(\\log \\tau^*)$ approximation factor for this problem, where $\\tau^*$ is the value of the optimal fractional solution. To achieve the $O(\\log \\tau^*)$ factor we employ a bootstrapping technique.<\/jats:p>","DOI":"10.1137\/s0895480195291874","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"255-267","source":"Crossref","is-referenced-by-count":25,"title":["Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications"],"prefix":"10.1137","volume":"13","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":"Baruch","family":"Schieber","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,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"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":"publisher","DOI":"10.1159\/000022781"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1093\/hmg\/5.7.1051"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3sSimonovits, Paul Erdo\u02dds\u2019 influence on extremal graph theory, Algorithms Combin., Vol. 14, Springer, Berlin, 1997, 148\u201319297h:05092","DOI":"10.1007\/978-3-642-60406-5_15"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00021-2"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"R10","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 Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1995, pp. 62\u201371; J. ACM, to appear.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"GuyEven, JosephNaor, LeonidZosin, An 8\u2010approximation algorithm for the subset feedback vertex set problem, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 310\u20133191450629","DOI":"10.1109\/SFCS.1996.548490"},{"key":"R12","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, CA, 1979."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"R14","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\u2010Verlag, New York, 1994, pp. 487\u2013498.","DOI":"10.1007\/3-540-58201-0_92"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"R16","unstructured":"D. S. Hochbaum,\n                      Chapter 9: Good, better, best, and better than best approximation algorithms\n                      , in Approximation Algorithms for NP\u2010Hard Problems, D. S. Hochbaum, ed., PWS Publishing Company, Boston, MA, 1996."},{"key":"R17","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, New York, 1972, pp. 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0833"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"T. Leighton and S. Rao,\n                      An approximate max\u2010flow min\u2010cut theorem for uniform multi\u2010commodity flow problems with applications to approximation algorithms\n                      , in Proceedings of the 29th Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 422\u2013431; J. ACM, to appear.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"R20","unstructured":"J. Ott,\n                      Analysis of Human Genetic Linkage\n                      , revised ed., The John Hopkins University Press, Baltimore and London, 1991."},{"key":"R21","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"Pearl Judea","year":"1988"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480195291874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:10:00Z","timestamp":1787317800000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480195291874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0895480195291874"],"URL":"https:\/\/doi.org\/10.1137\/s0895480195291874","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}