Feedback vertex set with neighbors

The feedback vertex set problem asks to find a minimum set of vertices such that the remaining graph after the vertices are deleted has no cycles. This is a classical NP-hard problem, so there is interest approximation algorithms for this problem. Another related problem asks to find a connected set of vertices, that, when deleted, remove all cycles from the graph. This work focuses on a slightly more general form of the problem, that only requires the vertices to be deleted be adjacent to at least one other vertex in the set of vertices to be deleted. An approximation algorithm and hardness of approximation result is presented for the problem.

A writeup can be found here.