Computer Science – Data Structures and Algorithms
Scientific paper
2010-04-10
Computer Science
Data Structures and Algorithms
Scientific paper
We study the parameterized complexity of the {\sc feedback vertex set} problem ({\sc fvs}) on undirected graphs. We approach the problem by considering a variation of it, the {\sc disjoint feedback vertex set} problem ({\sc disjoint-fvs}), which finds a disjoint feedback vertex set of size $k$ when a feedback vertex set of a graph is given. We show that {\sc disjoint-fvs} admits a small kernel, and can be solved in polynomial time when the graph has a special structure that is closely related to the maximum genus of the graph. We then propose a simple branch-and-search process on {\sc disjoint-fvs}, and introduce a new branch-and-search measure. The branch-and-search process effectively reduces a given graph to a graph with the special structure, and the new measure more precisely evaluates the efficiency of the branch-and-search process. These algorithmic, combinatorial, and topological structural studies enable us to develop an $O(3.83^k kn^2)$ time parameterized algorithm for the general {\sc fvs} problem, improving the previous best algorithm of time $O(5^k k n^2)$ for the problem.
Cao Yixin
Chen Jianer
Liu Yang
No associations
LandOfFree
On Feedback Vertex Set, New Measure and New Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Feedback Vertex Set, New Measure and New Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Feedback Vertex Set, New Measure and New Structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-600184