In KD[79] Krishnamoorthy and Deo presented some 17 vertex-deletion problems which are NP-complete for arbitrary graphs. In addition they showed that many of these problems remain NP-complete when restricted to either planar graphs or bipartite graphs. This paper is an attempt to complete one aspect of their study by considering the algorithmic complexity of the same problems when restricted to trees.

We show that most of the corresponding edge deletion problems for trees have already been solved algorithmically, each in linear time, yet apparently none of the vertex deletion problems have been considered. We present linear time solutions to most of these problems.