Parameterized vertex deletion problems for hereditary graph classes with a block property

DOI10.1007/978-3-662-53536-3_20MaRDI QIDQ3181061zbMATH OpenOpenAlexFDO

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

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, http://eprints.sztaki.hu/9042/

Mathematics Subject Classification ID

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

Abstract: For a class of graphs $mathcalP$, the Bounded $mathcalP$-Block Vertex Deletion problem asks, given a graph $G$ on $n$ vertices and positive integers $k$ and $d$, whether there is a set $S$ of at most $k$ vertices such that each block of $G-S$ has at most $d$ vertices and is in $mathcalP$. We show that when $mathcalP$ satisfies a natural hereditary property and is recognizable in polynomial time, Bounded $mathcalP$-Block Vertex Deletion can be solved in time $2^{O(klogd)}{n}^{O(1)}$. When $mathcalP$ contains all split graphs, we show that this running time is essentially optimal unless the Exponential Time Hypothesis fails. On the other hand, if $mathcalP$ consists of only complete graphs, or only cycle graphs and $K_2$, then Bounded $mathcalP$-Block Vertex Deletion admits a $c^k{n}^{O(1)}$-time algorithm for some constant $c$ independent of $d$. We also show that Bounded $mathcalP$-Block Vertex Deletion admits a kernel with $O(k^2{d}^7)$ vertices.

Recommendations

• A polynomial kernel for block graph deletion
• A polynomial kernel for block graph deletion
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Tight running time lower bounds for vertex deletion problems
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

Cites work

• A 4k^2 kernel for feedback vertex set
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• A polynomial kernel for block graph deletion
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Faster deterministic \textsc{Feedback Vertex Set}
• Finding odd cycle transversals.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 6784975 (Why is no real title available?)
• Parameterized algorithms for even cycle transversal
• The complexity of some edge deletion problems
• The node-deletion problem for hereditary properties is NP-complete
• Which problems have strongly exponential complexity?

Cited in

(15)

• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• Faster deterministic algorithm for cactus vertex deletion
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• A polynomial kernel for block graph deletion
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Tight running time lower bounds for vertex deletion problems
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• A polynomial kernel for block graph deletion
• Slightly superexponential parameterized problems
• Block elimination distance
• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Faster parameterized algorithm for r-pseudoforest deletion

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Parameterized vertex deletion problems for hereditary graph classes with a block property

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