## Abstract

We improve on the classical Nemhauser-Trotter Theorem, which is a key tool for the Minimum (Weighted) Vertex Cover problem in the design of both, approximation algorithms and exact fixed-parameter algorithms. Namely, we provide in polynomial time for a graph *G* with vertex weights *w* : *V* →〈0, ∞ 〉 a partition of *V* into three subsets *V* _{0}, *V* _{1}, V12
, with no edges between *V* _{0} and V12
or within *V* _{0}, such that the size of a minimum vertex cover for the graph induced by V12
is at least 12w(V12)
, and *every* minimum vertex cover *C* for (*G*, *w*) satisfies V1⊆C⊆V1∪V12
.

We also demonstrate one of possible applications of this strengthening of NT-Theorem for fixed parameter tractable problems related to Min-VC: for an integer parameter *k* to find all minimum vertex covers of size at most *k*, or to find a minimum vertex cover of size at most *k* under some additional constraints.

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

Title of host publication | Algorithm theory - SWAT 2004 |

Subtitle of host publication | 9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings |

Editors | Torben Hagerup , Jyrki Katajainen |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 174-186 |

ISBN (Electronic) | 9783540278108 |

ISBN (Print) | 9783540223399 |

DOIs | |

Publication status | Published - 2004 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 3111 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |