Processing math: 100%
Center for Algorithms and Theory of Computation

CS 269S, Winter 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


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(ckn2) for some constant c.

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