A parameterized algorithm for bounded-degree vertex deletion

DOI10.1007/978-3-319-42634-1_7MaRDI QIDQ2817850zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsparameterized algorithmsbounded-degree vertex deletionhitting set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: The $d$-bounded-degree vertex deletion problem, to delete at most $k$ vertices in a given graph to make the maximum degree of the remaining graph at most $d$, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the $(d+2)$-hitting set problem and generates the famous vertex cover problem. The $d$-bounded-degree vertex deletion problem is NP-hard for each fixed $dgeq0$. In terms of parameterized complexity, the problem parameterized by $k$ is W[2]-hard for unbounded $d$ and fixed-parameter tractable for each fixed $dgeq0$. Previously, (randomized) parameterized algorithms for this problem with running time bound $O^{\ast }((d+1{)}^k)$ are only known for $dleq2$. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in $O^{\ast }((d+1{)}^k)$ time for each $dgeq3$. Note that it is an open problem whether the $d^{\prime }$-hitting set problem can be solved in $O^{\ast }((d^{\prime }-1{)}^k)$ time for $d^{\prime }geq3$. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of $O^{\ast }(3.0645^k)$ for the case that $d=2$, improving the previous deterministic bound of $O^{\ast }(3.24^k)$.

Recommendations

• On structural parameterizations of the bounded-degree vertex deletion problem
• On bounded-degree vertex deletion parameterized by treewidth
• On structural parameterizations of the bounded-degree vertex deletion problem
• Bounded-degree techniques accelerate some parameterized graph algorithms
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion

Cites work

• A faster FPT algorithm for 3-path vertex cover
• A fixed-parameter algorithm for the vertex cover P₃ problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A graph‐theoretic generalization of the clique concept
• A linear kernel for co-path/cycle packing
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Every property of hyperfinite graphs is testable
• Exact exponential algorithms.
• Improved upper bounds for vertex cover
• On bounded-degree vertex deletion parameterized by treewidth
• Parameterized algorithmics for \(d\)-HITTING SET
• Parameterized algorithms for d-hitting set: the weighted case
• Randomized parameterized algorithms for P₂-packing and co-path packing problems

Cited in

(23)

• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• On making a distinguished vertex minimum degree by vertex deletion
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Structural parameterizations for two bounded degree problems revisited
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Faster parameterized algorithm for pumpkin vertex deletion set
• On bounded-degree vertex deletion parameterized by treewidth
• On structural parameterizations of the bounded-degree vertex deletion problem
• A linear kernel for co-path/cycle packing
• scientific article; zbMATH DE number 7525474 (Why is no real title available?)
• Parameterized orientable deletion
• Parameterized orientable deletion
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Solving Co-Path/Cycle Packing and Co-Path Packing faster than \(3^k\)
• Solving Co-Path/Cycle Packing and Co-Path Packing faster than \(3^k\)
• On the complexity of singly connected vertex deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• A \(5k\)-vertex kernel for 3-path vertex cover
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• An improved deterministic parameterized algorithm for cactus vertex deletion
• On making a distinguished vertex of minimum degree by vertex deletion

This page was built for publication: A parameterized algorithm for bounded-degree vertex deletion

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