A Naive Algorithm for Feedback Vertex Set
2017
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\cdot n^2)$ for some constant $c$.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
11
References
1
Citations
NaN
KQI