A Naive Algorithm for Feedback Vertex Set
Yixin Cao · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
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.