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

Chlebík, Miroslav and Chlebíková, Janka (2004) Improvement of Nemhauser-Trotter theorem and its applications in parametrized complexity. In: 9th Scandinavian Workshop on Algorithm Theory, Louisiana Museum Modern Art, Humlebaek, DENMARK.

Full text not available from this repository.


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, infinity) a partition of V into three subsets V-0, V-1, V-1/(2), with no edges between V-0 and V-1/(2) or within V-0, such that the size of a minimum vertex cover for the graph induced by V-1/(2) is at 2 least (1)/(2)w(V-1/(2)), and every minimum vertex cover C for (G,w) satisfies V1 subset of or equal to C subset of or equal to V1 boolean OR V-1/(2) 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.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Algorithm Theory - SWAT 2004
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 19:14
Last Modified: 04 Apr 2012 08:15
📧 Request an update