An FPT algorithm for Tree Deletion Set

Abstract

We give a 5^k n^O(1) time fixed-parameter algorithm for determining whether a given undirected graph on n vertices has a subset of at most k vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set.