### Abstract

Original language | English |
---|---|

Pages (from-to) | 1141-1158 |

Number of pages | 18 |

Journal | Journal of Computer and System Sciences |

Volume | 77 |

Issue number | 6 |

DOIs | |

Publication status | Published - Nov 2011 |

### Fingerprint

### Cite this

*Journal of Computer and System Sciences*,

*77*(6), 1141-1158. https://doi.org/10.1016/j.jcss.2010.12.001

}

*Journal of Computer and System Sciences*, vol. 77, no. 6, pp. 1141-1158. https://doi.org/10.1016/j.jcss.2010.12.001

**A generalization of Nemhauser and Trotters local optimization theorem.** / Fellows, Michael; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - A generalization of Nemhauser and Trotters local optimization theorem

AU - Fellows, Michael

AU - Guo, Jiong

AU - Moser, Hannes

AU - Niedermeier, Rolf

PY - 2011/11

Y1 - 2011/11

N2 - The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.

AB - The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotters result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away "easy parts" of the input instance, finally leaving a "hard core" whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d≥0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser-Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d≤1 and, for any ω>0, an O(k1+ω)-vertex problem kernel for d≥2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.

KW - Graph algorithms

KW - Kernelization

KW - NP-HARD problem

KW - Parameterized

KW - Polynomial-time

KW - Approximation algorithms

KW - Data reduction

KW - Linear programming

KW - Optimization

KW - Parameterization

KW - Computational complexity

UR - http://www.scopus.com/inward/record.url?scp=80052336275&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2010.12.001

DO - 10.1016/j.jcss.2010.12.001

M3 - Article

VL - 77

SP - 1141

EP - 1158

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 6

ER -