Hitting minors on bounded treewidth graphs. III. Lower bounds

DOI10.1016/J.JCSS.2019.11.002MaRDI QIDQ2301360zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/2103.06614, https://hal-lirmm.ccsd.cnrs.fr/lirmm-02989938/file/JCSS-D-19-00030-R1.pdf

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• 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
• A near-optimal planarization algorithm
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Fundamentals of parameterized complexity
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Graph theory
• Graph theory
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Lower bounds based on the exponential time hypothesis
• Node-and edge-deletion NP-complete problems
• On problems without polynomial kernels
• On the vertex cover \(P_3\) problem parameterized by treewidth
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Parameterized algorithms
• Planar Formulae and Their Uses
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Which problems have strongly exponential complexity?

Cited in

(11)

• Hitting minors on bounded treewidth graphs. I: General upper bounds
• 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
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Faster parameterized algorithms for modification problems to minor-closed classes
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• 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
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth

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)