On feedback vertex set new measure and new structures

Yixin Cao, Jianer Chen, Yang Liu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

63 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationAlgorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
Pages93-104
Number of pages12
DOIs
Publication statusPublished - 21 Jul 2010
Externally publishedYes
Event12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010 - Bergen, Norway
Duration: 21 Jun 201023 Jun 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6139 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
CountryNorway
CityBergen
Period21/06/1023/06/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this