Faster parameterized algorithms for modification problems to minor-closed classes

DOI10.46298/THEORETICS.24.19zbMATH Open1547.05284MaRDI QIDQ6601299FDOQ6601299

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

Publication date: 10 September 2024

Published in: TheoretiCS (Search for Journal in Brave)

Recommendations

• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Block elimination distance
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• scientific article; zbMATH DE number 1830723

zbMATH Keywords

graph minorsparameterized algorithmsgraph modification problemsobstruction setvertex deletionirrelevant vertex techniqueelimination distanceflat Wall theorem

Mathematics Subject Classification ID

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

Cites Work

• Fundamentals of parameterized complexity
• Graph minors. XX: Wagner's conjecture
• The node-deletion problem for hereditary properties is NP-complete
• Which problems have strongly exponential complexity?
• The extremal function for complete minors
• Graph minors. XIII: The disjoint paths problem
• Parametrized complexity theory.
• Complexity of Finding Embeddings in a k-Tree
• Title not available (Why is that?)
• Parameterized algorithms
• Title not available (Why is that?)
• Graph minors. V. Excluding a planar graph
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• The disjoint paths problem in quadratic time
• Treewidth. Computations and approximations
• Sparsity. Graphs, structures, and algorithms
• Parameterized and Exact Computation
• Graph theory
• Graph isomorphism parameterized by elimination distance to bounded degree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XXII. Irrelevant vertices in linkage problems
• An improved algorithm for finding tree decompositions of small width
• Faster parameterized algorithms for minor containment
• Graph minors. XVI: Excluding a non-planar graph
• Irrelevant vertices for the planar disjoint paths problem
• Forbidden graphs for tree-depth
• Obtaining a planar graph by vertex deletion
• Title not available (Why is that?)
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Title not available (Why is that?)
• A Menger-like property of tree-width: The finite case
• Upper bounds on the size of obstructions and intertwines
• A new proof of the flat wall theorem
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• A near-optimal planarization algorithm
• Data-compression for parametrized counting problems on sparse graphs
• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Title not available (Why is that?)
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Cutwidth: obstructions and algorithmic aspects
• Linear kernels for edge deletion problems to immersion-closed graph classes
• Fixed-parameter tractable distances to sparse graph classes
• A unified treatment of linked and lean tree-decompositions
• A faster parameterized algorithm for treedepth
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Vertex deletion parameterized by elimination distance and even less
• A Menger-like property of tree-cut width
• Linear rank-width of distance-hereditary graphs
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Deleting vertices to graphs of bounded genus
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Hitting topological minors is FPT
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• Parameterized complexity of elimination distance to first-order logic properties
• On the Parameterized Complexity of Clique Elimination Distance
• Sparse obstructions for minor-covering parameters
• Planarity Allowing Few Error Vertices in Linear Time
• Combing a Linkage in an Annulus
• 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

Cited In (1)

• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms

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)