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.

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, 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
URI:	http://sro.sussex.ac.uk/id/eprint/19674

📧 Request an update