An improved exact algorithm for undirected feedback vertex set

作者：Xiao, Mingyu^*; Nagamochi, Hiroshi

来源：Journal of Combinatorial Optimization, 2015, 30(2): 214-241.

DOI：10.1007/s10878-014-9737-x

• Exact exponential algorithms
• Feedback vertex set
• Measure and conquer
• Branch and bound

A feedback vertex set in an undirected graph is a subset of vertices removal of which leaves a graph with no cycles. Razgon (in: Proceedings of the 10th Scandinavian workshop on algorithm theory (SWAT 2006), pp. 160-171, 2006) gave a -time algorithm for finding a minimum feedback vertex set in an -vertex undirected graph, which is the first exact algorithm for the problem that breaks the trivial barrier of . Later, Fomin et al. (Algorithmica 52:293-307, 2008) improved the result to . In this paper, we further improve the result to . Our algorithm is analyzed by the measure-and-conquer method. We get the improvement by designing new reductions based on biconnectivity of instances and introducing a new measure scheme on the structure of reduced graphs.

• 出版日期2015-8
• 单位电子科技大学