Back to Search
Start Over
Hitting minors on bounded treewidth graphs. III. Lower bounds.
- Source :
-
Journal of Computer & System Sciences . May2020, Vol. 109, p56-77. 22p. - Publication Year :
- 2020
-
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 b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log tw). [ABSTRACT FROM AUTHOR]
- Subjects :
- *MATROIDS
*GRAPH connectivity
*MINORS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 109
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 141239473
- Full Text :
- https://doi.org/10.1016/j.jcss.2019.11.002