## Abstract

For a finite collection of graphs F, the F-M-Deletion problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function f_{F} such that F-M-Deletion can be solved in time f_{F}(tw) · n^{O(1)} on n-vertex graphs. We prove that f_{F}(tw) = 2^{2O}(tw·log tw) for every collection F, that f_{F}(tw) = 2^{O}(tw·log tw) if F contains a planar graph, and that f_{F}(tw) = 2^{O}(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic.

Original language | English (US) |
---|---|

Pages (from-to) | 1623-1648 |

Number of pages | 26 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 34 |

Issue number | 3 |

DOIs | |

State | Published - 2020 |

## Keywords

- Dynamic programming
- Exponential time hypothesis
- Graph minors
- Hitting minors
- Parameterized complexity
- Topological minors
- Treewidth

## ASJC Scopus subject areas

- General Mathematics