{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T17:51:31Z","timestamp":1792691491486,"version":"4.5.0"},"reference-count":28,"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":[[1998,1]]},"abstract":"<jats:p>A feedback vertex set of an undirected graph is a subset of vertices that intersects with the vertex set of each cycle in the graph. Given an undirected graph G with n vertices and weights on its vertices, polynomial-time algorithms are provided for approximating the problem of finding a feedback vertex set of G with smallest weight. When the weights of all vertices in G are equal, the performance ratio attained by these algorithms is 4-(2\/n). This improves a previous algorithm which achieved an approximation factor of $O(\\sqrt{\\log n})$ for this case. For general vertex weights, the performance ratio becomes $\\min\\{2\\Delta^2, 4 \\log_2 n\\}$ where $\\Delta$ denotes the maximum degree in G. For the special case of planar graphs this ratio is reduced to 10. An interesting special case of weighted graphs where a performance ratio of 4-(2\/n) is achieved is the one where a prescribed subset of the vertices, so-called blackout vertices, is not allowed to participate in any feedback vertex set.<\/jats:p>\n                  <jats:p>It is shown how these algorithms can improve the search performance for constraint satisfaction problems. An application in the area of Bayesian inference of graphs with blackout vertices is also presented.<\/jats:p>","DOI":"10.1137\/s0097539796305109","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"942-959","source":"Crossref","is-referenced-by-count":120,"title":["Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference"],"prefix":"10.1137","volume":"27","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Geiger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron M.","family":"Roth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"V. Bafna, P. Berman, and T. Fujito,\n                      Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs\n                      , in ISAAC 95, Algorithms and Computation, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds., Lecture Notes in Computer Science 1004, Springer\u2010Verlag, 1995, pp. 142\u2013151.","DOI":"10.1007\/BFb0015417"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. Bar\u2010Yehuda, S. Even, A local\u2010ratio theorem for approximating the weighted vertex cover problem, North\u2010Holland Math. Stud., Vol. 109, North\u2010Holland, Amsterdam, 1985, 27\u20134587h:05158","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"R4","unstructured":"R. Bar\u2010Yehuda, D. Geiger, J. Naor, and R. M. Roth,\n                      Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference\n                      , in Proceedings of the 5th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, Arlington, VA, 1994, pp. 344\u2013354."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00004-6"},{"key":"R6","unstructured":"R. Dechter and J. Pearl,\n                      The cycle cutset method for improving search performance in AI\n                      , in Proceedings 3rd IEEE on AI Applications, Orlando, FL, 1987."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90002-6"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90046-3"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1962.9.1-2.02"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Dan Geiger, Judea Pearl, On the logic of causal models, Mach. Intelligence Pattern Recogn., Vol. 9, North\u2010Holland, Amsterdam, 1990, 3\u2013141166825","DOI":"10.1016\/B978-0-444-88650-7.50006-8"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200504"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90080-X"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1036"},{"key":"R19","unstructured":"H. Kim and J. Pearl,\n                      A computational model for combined causal and diagnostic reasoning in inference systems\n                      , in Proceedings of the Eighth IJCAI, Morgan\u2013Kaufmann, San Mateo, CA, 1983, pp. 190\u2013193."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R21","unstructured":"B. Monien, R. Schulz, Four approximation algorithms for the feedback vertex set problem, Hanser, Munich, 1982, 315\u201332684m:68055"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90072-X"},{"key":"R23","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"Pearl Judea","year":"1988"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020974"},{"key":"R25","unstructured":"J. Stillman,\n                      On heuristics for finding loop cutsets in multiply connected belief networks\n                      , in Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, Cambridge, MA, 1990, pp. 265\u2013272."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0888-613X(90)90003-K"},{"key":"R27","unstructured":"T. Verma and J. Pearl,\n                      Causal networks: Semantics and expressiveness\n                      , in Proceedings of Fourth Workshop on Uncertainty in Artificial Intelligence, Minneapolis, MN, Association for Uncertainty in Artificial Intelligence, Mountain View, CA, 1988, pp. 352\u2013359."},{"key":"R28","unstructured":"H.\u2010J. Voss, Some properties of graphs containing k independent circuits, Academic Press, New York, 1968, 321\u201333439:2659"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796305109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:11:58Z","timestamp":1787335918000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796305109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539796305109"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796305109","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}