## Abstract

For a finite 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 provide lower bounds under the ETH on 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, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f_{F}(tw)=2^{Ω(tw)}, even if G is planar. Our main result is that if F contains a single connected graph H that is either P_{5} or is not a minor of the banner, then f_{F}(tw)=2^{Ω(tw⋅logtw)}.

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

Pages (from-to) | 56-77 |

Number of pages | 22 |

Journal | Journal of Computer and System Sciences |

Volume | 109 |

DOIs | |

State | Published - May 2020 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics