Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes

DOI10.1137/18M1228839zbMath1461.05164arXiv1609.07780OpenAlexW3121848388MaRDI QIDQ5150814

Marcin Wrochna, Dimitrios M. Thilikos, Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond

Publication date: 15 February 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

immersionskernelizationgraph modification problemstree-cut widthedge-deletion distance

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

On objects dual to tree-cut decompositions ⋮ Clique immersion in graph products ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Effective computation of immersion obstructions for unions of graph classes
• A minimum degree condition forcing complete graph immersion
• The structure of graphs not admitting a fixed immersion
• Graph minors. XX: Wagner's conjecture
• On an edge ranking problem of trees and graphs
• Parameterized graph separation problems
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. V. Excluding a planar graph
• Call routing and the ratcatcher
• Edge ranking of graphs is hard
• An FPT 2-approximation for tree-cut decomposition
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Graph minors. XIII: The disjoint paths problem
• Minors in graphs of large \(\theta_r\)-girth
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A Structure Theorem for Strong Immersions
• Excluded Grid Theorem
• Algorithmic Applications of Tree-Cut Width
• Polynomial Bounds for the Grid-Minor Theorem
• (Meta) Kernelization
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Easy problems for tree-decomposable graphs
• Uniform Kernelization Complexity of Hitting Forbidden Minors
• Fast Algorithms forK4Immersion Testing
• Complete graph immersions and minimum degree
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Immersions in Highly Edge Connected Graphs
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• (Meta) Kernelization
• Bidimensionality and Geometric Graphs
• Finding topological subgraphs is fixed-parameter tractable
• Cutwidth I: A linear time fixed parameter algorithm
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A weak immersion relation on graphs and its applications

This page was built for publication: Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes