A probabilistic analysis for the Feedback Vertex Set problem

Karthekeyan Chandrasekaran, CS (Mentor Santosh Vempala) - An important special case of the hitting set problem where the number of subsets to hit is exponential in the cardinality of the universal set X, is the Minimum Feedback Vertex Set (MFVS) problem. The MFVS problem is the following: given a graph G(V,E), find a subset S of vertices of smallest cardinality so that every cycle in the graph contains at least one vertex from S. If the graph has n vertices, then the number of possible cycles in the graph could be exponential in n. On the other hand, given any subset of vertices, one can quickly determine whether that subset is a FVS or find a cycle that is not hit by the subset. I would like to come up with a randomized algorithm that considers only a polynomial number of cycles in order to find a FVS whose cardinality is as close to that of the MFVS as possible. I will consider both the directed and undirected versions of this problem.