On Feedback Vertex Set: New Measure and New Structures

Yixin Cao, Jianer Chen, Yang Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)

Abstract

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 G\F 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.
Original languageEnglish
Pages (from-to)63-86
Number of pages24
JournalAlgorithmica
Volume73
Issue number1
DOIs
Publication statusPublished - 2 Sep 2015

Keywords

  • Cographic matroid
  • Cubic graphs
  • Disjoint feedback vertex set
  • Kernlization
  • Matroid intersection problem
  • Measure and bound
  • Parameterized computation

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this