A note on the minimum H-subgraph edge deletion

In this note we consider the following problem: Given a graph G and a subgraph H, what is the smallest subset E'⊆E(G) of edges in G that needs to be deleted from the graph to make it H free? Several algorithmic results are presented. First, using the general framework of Courcelle [9], we show that, for a fixed subgraph H, the problem can be solved in linear time on graphs of bounded treewidth. It is known that the constant hidden in the big-O notation of Courcelle algorithm is big which makes the approach impractical. Thus, we present two explicit linear time dynamic programming algorithms on graphs of bounded treewidth for restricted settings of the problem with reasonable constants. Third, using the linear time algorithm for graphs of bounded treewidth, we design a Baker's type polynomial time approximation scheme for the problem on planar graphs.