On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

DOI10.4230/LIPIcs.STACS.2018.33zbMath1487.68177OpenAlexW2793933268MaRDI QIDQ3304132

Sebastian Ordyniak, Fabian Klute, Robert Ganian

Publication date: 5 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2018.33

zbMATH Keywords

feedback vertex setparameterized algorithmsbounded-degree vertex deletiontreecut width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (11)

On the parameterized complexity of maximum degree contraction problem ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Unnamed Item ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Unnamed Item ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Combinatorial algorithms for the maximum \(k\)-plex problem
• The structure of graphs not admitting a fixed immersion
• A generalization of Nemhauser and Trotter's local optimization theorem
• Backdoors into heterogeneous classes of SAT and CSP
• On bounded-degree vertex deletion parameterized by treewidth
• Isolation concepts for efficiently enumerating dense subgraphs
• Meta-kernelization with structural parameters
• Treewidth. Computations and approximations
• The multidimensional 0-1 knapsack problem: an overview.
• Which problems have strongly exponential complexity?
• An FPT 2-approximation for tree-cut decomposition
• Reduction algorithms for graphs of small treewidth
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• A complete parameterized complexity analysis of bounded planning
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithmic Applications of Tree-Cut Width
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Integer Programming with a Fixed Number of Variables
• Solving Problems on Graphs of High Rank-Width
• A Linear Kernel for Co-Path/Cycle Packing
• A graph‐theoretic generalization of the clique concept
• Immersions in Highly Edge Connected Graphs
• Meta-kernelization using Well-structured Modulators
• Parameterized Algorithms

This page was built for publication: On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem