Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

243 Downloads (Pure)


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 languageEnglish
Title of host publicationAlgorithm theory - SWAT 2004
Subtitle of host publication9th Scandinaviaworkshop on algorithm theory, Humlebæk, Denmark, July 8-10, 2004. proceedings
EditorsTorben Hagerup , Jyrki Katajainen
Place of PublicationBerlin
ISBN (Electronic)9783540278108
ISBN (Print)9783540223399
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Improvement of Nemhauser-Trotter Theorem and its applications in parametrized complexity'. Together they form a unique fingerprint.

Cite this