## Abstract

For a fixed collection of graphs F, the F-M-Deletion problem consists in, given a graph G and an integer k, decide 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. Using and enhancing the machinery of boundaried graphs and small sets of representatives introduced by Bodlaender et al. [J ACM, 2016], we prove that when all the graphs in F are connected and at least one of them is planar, then f_{F}(w) = 2^{O(w·logw)}. When F is a singleton containing a clique, a cycle, or a path on i vertices, we prove the following asymptotically tight bounds: •f_{{K4}}(w) = 2^{Θ(w·log w)}.•f_{{Ci}}(w) = 2^{Θ(w)} for every i ≤ 4, and f_{{Ci}}(w) = 2^{Θ(w·log w)} for every i ≥ 5. • f_{{Pi}}(w) = 2Θ(w) for every i ≤ 4, and f_{{Pi}}(w) = 2^{Θ(w·log w)} for every i ≥ 6. The lower bounds hold unless the Exponential Time Hypothesis fails, and the superexponential ones are inspired by a reduction of Marcin Pilipczuk [Discrete Appl Math, 2016]. The singleexponential algorithms use, in particular, the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. We also consider the version of the problem where the graphs in F are forbidden as topological minors, and prove essentially the same set of results holds.

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

Title of host publication | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |

Editors | Daniel Lokshtanov, Naomi Nishimura |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959770514 |

DOIs | |

State | Published - Feb 1 2018 |

Event | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 - Vienna, Austria Duration: Sep 6 2017 → Sep 8 2017 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 89 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |
---|---|

Country/Territory | Austria |

City | Vienna |

Period | 9/6/17 → 9/8/17 |

## Keywords

- Dynamic programming
- Exponential Time Hypothesis
- Graph minors
- Hitting minors
- Parameterized complexity
- Topological minors
- Treewidth

## ASJC Scopus subject areas

- Software