A generalization of Nemhauser and Trotter's local optimization theorem

DOI10.1016/j.jcss.2010.12.001zbMath1235.68081OpenAlexW2125455032WikidataQ57359675 ScholiaQ57359675MaRDI QIDQ657921

Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Hannes Moser

Publication date: 11 January 2012

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.12.001

zbMATH Keywords

vertex coverbounded degree vertex deletionNemhauser-Trotter local optimization theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (35)

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths ⋮ Linear kernels for separating a graph into components of bounded size ⋮ Kernelization of the 3-path vertex cover problem ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Win-win kernelization for degree sequence completion problems ⋮ Isolation concepts for efficiently enumerating dense subgraphs ⋮ Edge-disjoint packing of stars and cycles ⋮ Graph isomorphism parameterized by elimination distance to bounded degree ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Approximating power node-deletion problems ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Looking at the stars
• Isolation concepts for efficiently enumerating dense subgraphs
• A new approach for approximating node deletion problems
• Threshold dominating sets and an improved characterization of \(W[2\)]
• Reduction algorithms for graphs of small treewidth
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Vertex Cover: Further Observations and Further Improvements
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
• Solving NP-hard semirandom graph problems in polynomial expected time
• An Improved Parameterized Algorithm for a Generalized Matching Problem
• A Linear Kernel for Co-Path/Cycle Packing
• Kernelization: New Upper and Lower Bound Techniques
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• A graph‐theoretic generalization of the clique concept
• A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
• Graph-Theoretic Concepts in Computer Science

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