Faster parameterized algorithms for modification problems to minor-closed classes

DOI10.46298/theoretics.24.19zbMATH Open1547.05284MaRDI QIDQ6601299

Giannos Stamoulis, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

Publication date: 10 September 2024

Published in: TheoretiCS (Search for Journal in Brave)

zbMATH Keywords

parameterized algorithmsgraph minorsobstruction setgraph modification problemsvertex deletionirrelevant vertex techniqueelimination distanceflat Wall theorem

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph isomorphism parameterized by elimination distance to bounded degree
• Irrelevant vertices for the planar disjoint paths problem
• Fundamentals of parameterized complexity
• The disjoint paths problem in quadratic time
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Forbidden graphs for tree-depth
• Sparsity. Graphs, structures, and algorithms
• Faster parameterized algorithms for minor containment
• A new proof of the flat wall theorem
• Graph minors. XX: Wagner's conjecture
• Graph minors. XXI. graphs with unique linkages
• Graph minors. V. Excluding a planar graph
• A Menger-like property of tree-width: The finite case
• The node-deletion problem for hereditary properties is NP-complete
• Upper bounds on the size of obstructions and intertwines
• Treewidth. Computations and approximations
• Graph minors. XVI: Excluding a non-planar graph
• Which problems have strongly exponential complexity?
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Cutwidth: obstructions and algorithmic aspects
• A unified treatment of linked and lean tree-decompositions
• The extremal function for complete minors
• Graph minors. XIII: The disjoint paths problem
• A Menger-like property of tree-cut width
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Sparse obstructions for minor-covering parameters
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• 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
• Fixed-parameter tractable distances to sparse graph classes
• Obtaining a planar graph by vertex deletion
• Parametrized complexity theory.
• Graph Theory
• A shorter proof of the graph minor algorithm
• Linear Rank-Width of Distance-Hereditary Graphs
• Complexity of Finding Embeddings in a k-Tree
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs
• Parameterized Complexity of Elimination Distance to First-Order Logic Properties
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
• Hitting topological minors is FPT
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• A Faster Parameterized Algorithm for Treedepth
• Planarity Allowing Few Error Vertices in Linear Time
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Parameterized and Exact Computation
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Combing a Linkage in an Annulus
• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Vertex deletion parameterized by elimination distance and even less
• On the Parameterized Complexity of Clique Elimination Distance
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
• Model-checking for first-order logic with disjoint paths predicates in proper minor-closed graph classes
• Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent
• Compound logics for modification problems
• Faster parameterized algorithms for modification problems to minor-closed classes

This page was built for publication: Faster parameterized algorithms for modification problems to minor-closed classes

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