A naive algorithm for feedback vertex set

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

4 Citations (Scopus)


Given a graph on n vertices and an integer k, the feedback vertex set problem asks for the deletion of at most k vertices to make the graph acyclic. We show that a greedy branching algorithm, which always branches on an undecided vertex with the largest degree, runs in single-exponential time, i.e., O(ck· n2) for some constant c.
Original languageEnglish
Title of host publication1st Symposium on Simplicity in Algorithms, SOSA 2018 - Co-located with the 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsRaimund Seidel
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770644
Publication statusPublished - 1 Jan 2018
Event1st Symposium on Simplicity in Algorithms, SOSA 2018 - New Orleans, United States
Duration: 7 Jan 201810 Jan 2018

Publication series

NameOpenAccess Series in Informatics
ISSN (Print)2190-6807


Conference1st Symposium on Simplicity in Algorithms, SOSA 2018
Country/TerritoryUnited States
CityNew Orleans


  • Analysis of algorithms
  • Branching algorithm
  • Graph modification problem
  • Greedy algorithm
  • Parameterized computation

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modelling and Simulation


Dive into the research topics of 'A naive algorithm for feedback vertex set'. Together they form a unique fingerprint.

Cite this