Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference

作     者：Bar-Yehuda, R Geiger, D Naor, J Roth, RM 

作者机构：Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel SUNY Buffalo Buffalo NY 14260 USA Rutgers State Univ DIMACS Piscataway NJ 08855 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1998年第27卷第4期

页      面：942-959页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：approximation algorithms vertex feedback set combinatorial optimization Bayesian networks constraint satisfaction 

摘      要：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(root 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. 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.