Hitting minors on bounded treewidth graphs. III. Lower bounds

Julien Baste; Ignasi Sau; Dimitrios M. Thilikos

doi:10.1016/j.jcss.2019.11.002

Hitting minors on bounded treewidth graphs. III. Lower bounds

Julien Baste, Ignasi Sau, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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₅ or is not a minor of the banner, then f_F(tw)=2^{Ω(tw⋅log⁡tw)}.

Original language	English (US)
Pages (from-to)	56-77
Number of pages	22
Journal	Journal of Computer and System Sciences
Volume	109
DOIs	https://doi.org/10.1016/j.jcss.2019.11.002
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
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2019.11.002

Cite this

@article{8d141ad7356a4b94acdf1b765bb2749b,

title = "Hitting minors on bounded treewidth graphs. III. Lower bounds",

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 fF such that F-M-DELETION can be solved in time fF(tw)⋅nO(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, fF(tw)=2Ω(tw), even if G is planar. Our main result is that if F contains a single connected graph H that is either P5 or is not a minor of the banner, then fF(tw)=2Ω(tw⋅log⁡tw).",

keywords = "Dynamic programming, Exponential Time Hypothesis, Graph minors, Hitting minors, Parameterized complexity, Topological minors, Treewidth",

author = "Julien Baste and Ignasi Sau and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2020",

month = may,

doi = "10.1016/j.jcss.2019.11.002",

language = "English (US)",

volume = "109",

pages = "56--77",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Hitting minors on bounded treewidth graphs. III. Lower bounds

AU - Baste, Julien

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

PY - 2020/5

Y1 - 2020/5

N2 - 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 fF such that F-M-DELETION can be solved in time fF(tw)⋅nO(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, fF(tw)=2Ω(tw), even if G is planar. Our main result is that if F contains a single connected graph H that is either P5 or is not a minor of the banner, then fF(tw)=2Ω(tw⋅log⁡tw).

AB - 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 fF such that F-M-DELETION can be solved in time fF(tw)⋅nO(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, fF(tw)=2Ω(tw), even if G is planar. Our main result is that if F contains a single connected graph H that is either P5 or is not a minor of the banner, then fF(tw)=2Ω(tw⋅log⁡tw).

KW - Dynamic programming

KW - Exponential Time Hypothesis

KW - Graph minors

KW - Hitting minors

KW - Parameterized complexity

KW - Topological minors

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85077355231&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85077355231&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2019.11.002

DO - 10.1016/j.jcss.2019.11.002

M3 - Article

AN - SCOPUS:85077355231

SN - 0022-0000

VL - 109

SP - 56

EP - 77

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Hitting minors on bounded treewidth graphs. III. Lower bounds

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this