On a generalization of Nemhauser and Trotter's local optimization theorem

DOI10.1007/978-3-662-48971-0_38zbMath1353.68138arXiv1601.00164OpenAlexW2231757830MaRDI QIDQ340561

Mingyu Xiao

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences, Algorithms and Computation (Search for Journal in Brave)

Abstract: Fellows, Guo, Moser and Niedermeier~[JCSS2011] proved a generalization of Nemhauser and Trotter's theorem, which applies to extsc{Bounded-Degree Vertex Deletion} (for a fixed integer $dgeq 0$, to delete $k$ vertices of the input graph to make the maximum degree of it $leq d$) and gets a linear-vertex kernel for $d=0$ and $1$, and a superlinear-vertex kernel for each $dgeq 2$. It is still left as an open problem whether extsc{Bounded-Degree Vertex Deletion} admits a linear-vertex kernel for each $dgeq 3$. In this paper, we refine the generalized Nemhauser and Trotter's theorem and get a linear-vertex kernel for each $dgeq 0$.

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

zbMATH Keywords

graph theorygraph algorithmsgraph decompositionkernelizationfixed-parameter tractablebounded-degree vertex deletion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• A generalization of Nemhauser and Trotter's local optimization theorem
• On bounded-degree vertex deletion parameterized by treewidth
• Looking at the stars
• Isolation concepts for efficiently enumerating dense subgraphs
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Vertex Cover: Further Observations and Further Improvements
• A Parameterized Algorithm for Bounded-Degree Vertex Deletion
• A 4 k ² kernel for feedback vertex set
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
• A Note on Vertex Cover in Graphs with Maximum Degree 3
• A Linear Kernel for Co-Path/Cycle Packing
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• A graph‐theoretic generalization of the clique concept
• Improved Algorithms for Bipartite Network Flow
• Faster Parameterized Algorithms Using Linear Programming
• A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Graph-Theoretic Concepts in Computer Science

Related Items (13)

Linear kernels for separating a graph into components of bounded size ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Edge-disjoint packing of stars and cycles ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Approximating power node-deletion problems ⋮ Approximating power node-deletion problems ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Kernels for packing and covering problems ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

This page was built for publication: On a generalization of Nemhauser and Trotter's local optimization theorem