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)

Abstract

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
Volume61
ISBN (Electronic)9783959770644
DOIs
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
Volume61
ISSN (Print)2190-6807

Conference

Conference1st Symposium on Simplicity in Algorithms, SOSA 2018
CountryUnited States
CityNew Orleans
Period7/01/1810/01/18

Keywords

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

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modelling and Simulation

Cite this