TY - GEN
T1 - On feedback vertex set new measure and new structures
AU - Cao, Yixin
AU - Chen, Jianer
AU - Liu, Yang
PY - 2010/7/21
Y1 - 2010/7/21
N2 - We study the parameterized complexity of the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (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 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 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.83kkn2) time parameterized algorithm for the general fvs problem, improving the previous best algorithm of time O(5kkn2) for the problem.
AB - We study the parameterized complexity of the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (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 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 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.83kkn2) time parameterized algorithm for the general fvs problem, improving the previous best algorithm of time O(5kkn2) for the problem.
UR - http://www.scopus.com/inward/record.url?scp=77954644038&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13731-0_10
DO - 10.1007/978-3-642-13731-0_10
M3 - Conference article published in proceeding or book
SN - 364213730X
SN - 9783642137303
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 93
EP - 104
BT - Algorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
T2 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
Y2 - 21 June 2010 through 23 June 2010
ER -