Hitting minors on bounded treewidth graphs. III. Lower bounds

DOI10.1016/J.JCSS.2019.11.002zbMATH Open1435.68121arXiv2103.06614OpenAlexW2996174063MaRDI QIDQ2301360FDOQ2301360

Authors: Julien Baste, Ignasi Sau, Dimitrios M. Thilikos 

Publication date: 24 February 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: For a finite collection of graphs $calF$, the $calF$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $SsubseteqV(G)$ with $|S|leqk$ such that $GsetminusS$ does not contain any of the graphs in $calF$ as a minor. We are interested in the parameterized complexity of $calF$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed $calF$, the smallest function $f_{calF}$ such that $calF$-M-DELETION can be solved in time $f_{calF}(tw)cdot{n}^{O(1)}$ on $n$-vertex graphs. We provide lower bounds under the ETH on $f_{calF}$ for several collections $calF$. We first prove that for any $calF$ containing connected graphs of size at least two, $f_{calF}(tw)=2^{Omega(tw)}$, even if the input graph $G$ is planar. Our main contribution consists of superexponential lower bounds for a number of collections $calF$, inspired by a reduction of Bonnet et al.~[IPEC, 2017]. In particular, we prove that when $calF$ contains a single connected graph $H$ that is either $P_5$ or is not a minor of the banner (that is, the graph consisting of a $C_4$ plus a pendent edge), then $f_{calF}(tw)=2^{Omega(twcdotlogtw)}$. This is the third of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $H$-M-DELETION, in terms of $H$, when $H$ is connected.

Full work available at URL: https://arxiv.org/abs/2103.06614

Recommendations

• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• A complexity dichotomy for hitting small planar minors parameterized by treewidth

zbMATH Keywords

dynamic programmingtreewidthexponential time hypothesisgraph minorsparameterized complexitytopological minorshitting minors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Graph theory
• Graph theory
• Fundamentals of parameterized complexity
• On problems without polynomial kernels
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Planar Formulae and Their Uses
• Lower bounds based on the exponential time hypothesis
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized algorithms
• Node-and edge-deletion NP-complete problems
• On the vertex cover \(P_3\) problem parameterized by treewidth
• Title not available (Why is that?)
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• A near-optimal planarization algorithm
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• A complexity dichotomy for hitting small planar minors parameterized by treewidth
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• The role of planarity in connectivity problems parameterized by treewidth

Cited In (11)

• Hitting minors on bounded treewidth graphs. I: General upper bounds
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Title not available (Why is that?)
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Faster parameterized algorithms for modification problems to minor-closed classes
• \(K_{a,k}\) minors in graphs of bounded tree-width
• A complexity dichotomy for hitting small planar minors parameterized by treewidth
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm

This page was built for publication: Hitting minors on bounded treewidth graphs. III. Lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301360)