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

bounded-degree vertex deletiongraph algorithmshitting setparameterized algorithms

Mathematics Subject Classification ID

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

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)

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

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)