Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
From MaRDI portal
Publication:5130572
DOI10.1137/19M1287146zbMath1450.05084arXiv1704.07284OpenAlexW3045943679MaRDI QIDQ5130572
Ignasi Sau, Julien Baste, Dimitrios M. Thilikos
Publication date: 28 October 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.07284
dynamic programmingtreewidthparameterized complexitygraph minorsexponential time hypothesistopological minorshitting minors
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
\(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Faster parameterized algorithms for minor containment
- A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
- Graph minors. V. Excluding a planar graph
- The node-deletion problem for hereditary properties is NP-complete
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Which problems have strongly exponential complexity?
- Reduction algorithms for graphs of small treewidth
- Graph minors. XIII: The disjoint paths problem
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Deleting vertices to graphs of bounded genus
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Planar graphs, via well-orderly maps and trees
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Dynamic Programming for H-minor-free Graphs
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- (Meta) Kernelization
- Explicit Linear Kernels via Dynamic Programming
- A Census of Planar Triangulations
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- A Set of Topological Invariants for Graphs
- Topological cliques in graphs II
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- A Near-Optimal Planarization Algorithm
- Bidimensionality and Geometric Graphs
- Finding topological subgraphs is fixed-parameter tractable
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Dynamic programming for graphs on surfaces
- Parameterized Algorithms
- Slightly Superexponential Parameterized Problems
- Hitting and Harvesting Pumpkins
- Encyclopedia of Algorithms
- On the number of labeled graphs of bounded treewidth
This page was built for publication: Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
