An FPT algorithm for elimination distance to bounded degree graphs

DOI10.4230/LIPICS.STACS.2021.5MaRDI QIDQ7231528zbMATH OpenFDO

Authors Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh

Publication date 21 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2021.5

zbMATH Keywords

fixed-parameter tractabilitygraph modificationelimination distance

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
• Combining treewidth and backdoors for CSP
• Designing FPT algorithms for cut problems using randomized contractions
• Easy problems for tree-decomposable graphs
• Elimination Distance to Bounded Degree on Planar Graphs
• Elimination distances, blocking sets, and kernels for Vertex Cover
• Fixed-parameter tractable distances to sparse graph classes
• Graph isomorphism parameterized by elimination distance to bounded degree
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Meta-kernelization using Well-structured Modulators
• On tractable parameterizations of graph isomorphism
• Parameterized algorithms
• Parameterized and Exact Computation
• Reducing CMSO model checking to highly connected graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth computation and extremal combinatorics

This page was built for publication: An FPT algorithm for elimination distance to bounded degree graphs

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