2026-08-12T12:57:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8296 2024-03-06T10:30:15Z ddc:004 open_access

A Naive Algorithm for Feedback Vertex Set Cao, Yixin greedy algorithm analysis of algorithms branching algorithm parameterized computation -- graph modification problem 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(c^k n^2) for some constant c. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yixin Cao 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.1 urn:nbn:de:0030-drops-82961 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.1 eng https://creativecommons.org/licenses/by/3.0/legalcode