Research On The Parameterized Feedback Vertex Set Problem

Feedback Vertex Set(FVS) problems are classical NP problems. There are important applications of these problems in many fields,such as circuit testing,deadlock resolution,network designing,analyzing manufacturing processes and computational biology.Many different algorithmic approaches were tried on this problem, including approximation algorithms,exact algorithms and probabilistic algorithms.The parameterized FVS problems have received considerable attention.The FVS problems both in directed and undirected graphs were proved to be fixed-parameterized tractable(FPT).In this paper,we give a fixed-parameter enumeration algorithm for the FVS problem by the branch-and-search method.In the algorithm,a FVS F with size of k is found firstly.Then the graph is partitioned by F and reduced into a specific structure by branch-and-search method,so that the FVS problem on the specific structure can be transformed to the Feedback Edge Set(FES) problem.Finally,the z minimum-weight FES are found by enumerating the z maximum-weight forests.Thus the z minimum-weight FVS of size k are found.The whole algorithm runs in time O(5~kkn~2+(5~k+3~kz)n~2 logn).Moreover,the parameterized weighted FVS problem which finds the minimum-weight FVS of size at most k in Tournaments is also discussed in this paper.In the algorithm for the problem,a FVS F with size of k is found firstly.Then the graph is partitioned by F.For each partition,the FVS problem is transformed into Common Susequence problem so that the minimum-weight FVS based on a partition can be found.The minimum one among the minimum-weight FVS based on each partition is the solution of the problem.We give two algorithms to solve the Common Susequence problem,one algorithm by the branch-and-search method and the other by the dynamic programming method.Then the parameterized weighted FVS problem is solvable in time O(3~kn) and O(2~kn~2(logn+k)). Finally,the study work on FVS problem in this paper is summed up and some future researches with considerable attention on FVS problems are proposed.