A Note on the Minimum H-Subgraph Edge Deletion

作者：Grigoriev Alexander^*; Marchal Bert; Usotskaya Natalya

来源：International Journal of Foundations of Computer Science, 2015, 26(3): 399-411.

DOI：10.1142/S0129054115500227

• Minimum edge deletion
• H-free graph
• bounded treewidth

In this note we consider the following problem: Given a graph G and a subgraph H, what is the smallest subset E' subset of 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 impiractical. 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.

• 出版日期2015-4