Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property

DOI10.1007/978-3-662-53536-3_20zbMath1417.68062arXiv1603.05945OpenAlexW2298830675MaRDI QIDQ3181061

O-joung Kwon, Nick Brettell, Dániel Marx, Édouard Bonnet

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.05945

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ A polynomial kernel for block graph deletion ⋮ Slightly Superexponential Parameterized Problems ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Unnamed Item ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Faster deterministic algorithm for cactus vertex deletion

Uses Software

• Algorithm 447

Cites Work

• Finding odd cycle transversals.
• On the computational complexity of vertex integrity and component order connectivity
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Which problems have strongly exponential complexity?
• Faster deterministic \textsc{Feedback Vertex Set}
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• The complexity of some edge deletion problems
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Parameterized Algorithms for Even Cycle Transversal
• Hitting and Harvesting Pumpkins
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property