On Feedback Vertex Set: New Measure and New Structures Academic Article uri icon

abstract

  • 2014, Springer Science+Business Media New York. We present a new parameterized algorithm for 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 feedback vertex set of size k that has no overlap with a given feedback vertex set F of the graph G. We develop an improved kernelization algorithm for disjoint-fvs and show that disjoint-fvs can be solved in polynomial time when all vertices in GF have degrees upper bounded by three. We then propose a new branch-and-search process on disjoint-fvs, and introduce a new branch-and-search measure. The process effectively reduces a given graph to a graph on which disjoint-fvs becomes polynomial-time solvable, and the new measure more accurately evaluates the efficiency of the process. These algorithmic and combinatorial studies enable us to develop an O(3.83k)-time parameterized algorithm for the general fvs problem, improving all previous algorithms for the problem.

published proceedings

  • ALGORITHMICA

altmetric score

  • 5.5

author list (cited authors)

  • Cao, Y., Chen, J., & Liu, Y.

citation count

  • 30

complete list of authors

  • Cao, Yixin||Chen, Jianer||Liu, Yang

publication date

  • September 2015