The maximum subforest problem: approximation and exact algorithms
Ron Shamir, Dekel Tsur · 1998
Abstract We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G0 of G such that G0 does not contain a subtree isomorphic to a tree from H, and the number of edges in G0 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 2O(k 2 / log k)n, where n is the number of vertices in G, and k is the total number of vertices in H.