Dekel Tsur

We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G′ of G such that G′ does not contain a subtree isomorphic to a tree from H, and the number of edges in G′ is maximum. We give a polynomial time approximation scheme for this problem. We also give an exact algorithm for this problem whose time complexity is 2^{O(k(2)/log k)}n, where n is the number of vertices in G, and k is the total number of vertices in H.