## February 16, 2018:

# A Naive Algorithm for Feedback Vertex Set

## Elham Havvaei

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$.

(Based
on a paper
from SOSA 2018 by Yixin Cao)