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

DOI10.1007/978-3-662-48971-0_38zbMATH Open1353.68138arXiv1601.00164OpenAlexW2231757830MaRDI QIDQ340561FDOQ340561

Authors: 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 $dgeq0$, to delete $k$ vertices of the input graph to make the maximum degree of it $leqd$) and gets a linear-vertex kernel for $d=0$ and $1$, and a superlinear-vertex kernel for each $dgeq2$. It is still left as an open problem whether extsc{Bounded-Degree Vertex Deletion} admits a linear-vertex kernel for each $dgeq3$. In this paper, we refine the generalized Nemhauser and Trotter's theorem and get a linear-vertex kernel for each $dgeq0$.

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

Recommendations

• On a generalization of Nemhauser and Trotter's local optimization theorem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A generalization of Nemhauser and Trotter's local optimization theorem
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• An extension of the Nemhauser-Trotter theorem to generalized vertex cover with applications

zbMATH Keywords

graph theorygraph algorithmsgraph decompositionkernelizationfixed-parameter tractablebounded-degree vertex deletion

Mathematics Subject Classification ID

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

Cites Work

• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• A 4 k ² kernel for feedback vertex set
• Hitting forbidden minors: approximation and kernelization
• A linear kernel for co-path/cycle packing
• A generalization of Nemhauser and Trotter's local optimization theorem
• Looking at the stars
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Vertex packings: Structural properties and algorithms
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• An extension of the Nemhauser-Trotter theorem to generalized vertex cover with applications
• A graph‐theoretic generalization of the clique concept
• Title not available (Why is that?)
• On bounded-degree vertex deletion parameterized by treewidth
• 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 note on vertex cover in graphs with maximum degree 3
• Improved Algorithms for Bipartite Network Flow
• Faster Parameterized Algorithms Using Linear Programming
• A generalization of Nemhauser and Trotter's local optimization theorem
• Graph-Theoretic Concepts in Computer Science
• Isolation concepts for efficiently enumerating dense subgraphs

Cited In (18)

• Approximating Partially Bounded Degree Deletion on Directed Graphs
• A generalization of Nemhauser and Trotter's local optimization theorem
• A Parameterized Algorithm for Bounded-Degree Vertex Deletion
• Approximating power node-deletion problems
• Approximating power node-deletion problems
• A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Local optimality of Zaks-Perles-Wills simplices
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Linear kernels for separating a graph into components of bounded size
• An extension of the Nemhauser-Trotter theorem to generalized vertex cover with applications
• Algorithm Theory - SWAT 2004
• A generalization of Nemhauser and Trotter's local optimization theorem
• Edge-disjoint packing of stars and cycles
• Kernels for packing and covering problems
• A \(5k\)-vertex kernel for 3-path vertex cover
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• Approximating Bounded Degree Deletion via Matroid Matching

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

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