A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs

DOI10.1137/21M1396824zbMath1489.05134MaRDI QIDQ5071096

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

Publication date: 20 April 2022

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

zbMATH Keywords

fixed-parameter tractabilitygraph modificationelimination distance

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Distance from triviality 2.0: hybrid parameterizations ⋮ First-order Logic with Connectivity Operators ⋮ Block elimination distance

Cites Work

• Graph isomorphism parameterized by elimination distance to bounded degree
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Treewidth computation and extremal combinatorics
• Fixed-parameter tractable distances to sparse graph classes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Combining Treewidth and Backdoors for CSP.
• On Tractable Parameterizations of Graph Isomorphism
• Reducing CMSO model checking to highly connected graphs
• Elimination Distance to Bounded Degree on Planar Graphs
• Parameterized and Exact Computation
• Meta-kernelization using Well-structured Modulators
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Elimination distances, blocking sets, and kernels for Vertex Cover

This page was built for publication: A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs