Faster parameterized algorithms for modification problems to minor-closed classes

DOI10.46298/THEORETICS.24.19MaRDI QIDQ6601299zbMATH OpenFDO

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

Publication date 10 September 2024

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.24.19

zbMATH Keywords

elimination distanceflat Wall theoremgraph minorsgraph modification problemsirrelevant vertex techniqueobstruction setparameterized algorithmsvertex deletion

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(3)

• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Compound logics for modification problems
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

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)