无向图中子集反馈顶点集问题的精确算法

Exact Algorithms for the Subset Feedback Vertex Set Problem in Undirected Graphs

子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~*(2~n)的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~*(1.8638n)的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~*(1.7743n).文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.

Since 1971 when Cook proposed NP and NP-complete concepts, NP theory has been widely studied. NP-completeness has become one of the most important concepts in computational theory. When P≠ NP, there is no polynomial time algorithm for any NP-complete problem. Exact algorithms aim to develop nontrivial fast exponential time algorithms for NP-complete and NP-hard problems. Some topics in this area, such as whether there is an algorithm faster than O＊ （2n） for TSP, whether the maximum independent set problem can be solved in O＊（1. 0001n） and so on, are well known hard tasks in exact algorithms and computational complexity. During the last 20 years, many elegant techniques have been developed to design exact algorithms and this area becomes a hot area in theoretical computer science. The measure-and-conquer method, introduced by Fomin et al. , is one of the most important methods to investigate exact algorithms and parameterized algorithms. This method is based on a kind of amortization analysis, in which we set different weights to each vertex and use the sum of all vertex weights as the measure to evaluate the problem size. Compared to traditional measures, the weighted measure may catch more structural information of the graph and lead to a further improvement without modifying the algorithms. Nowadays, for many important NP-hard problems, the best exact algorithms are designed and analyzed by this new method. The subset feedback vertex set problem is a classical NP-hard problem that has been extensively studied in exact algorithms. Given an undirected graph G= （V,E） and a set S V, the subset feedback vertex set problem asks us to delete a minimum number of vertices from G such that each vertex in S is not in any cycle in the remaining graph. This problem contains the feedback vertex set problem and the multiway cut problem as special cases. When S V includes all vertex of the graph, it is equivalent to the classical NP-hard feedback vertex set problem. When S V only contains one vertex and it does not allow to be delete, it can be transformed to the multiway cut problem. The subset feedback vertex set problem finds applications in circuit testing, network communication, deadlock recovery of operating system, synchronization system, artificial intelligence, biological computing and so on. The subset feedback vertex set problem is also an important problem in exact algorithms. A brute-force algorithm that tests each vertex subset of the graph gives a trivial running time bound of O＊（2n）, where n is the number of vertices in the graph. This trivial bound was not broken until recently Fomin et al. gave an O＊（1. 8638n）-time algorithm in 2011. This paper will further improve the running time bound to O＊ （1. 7743n）. The new algorithm is a branch-and-search algorithm that is analyzed by using the measure-and-conquer method. In order to get the improvement, this paper deeply analyzes the problem structural properties and explores a number of effective reduction and branching rules. With the help of the new reduction and branching rules, the measure-and-conquer method can reduce the problem instance effectively and then leads to the claimed running time bound.