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.
|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|
|Publication status||Published - 2004|
|Name||Lecture Notes in Computer Science|