On efficient fixed parameter algorithms for WEIGHTED VERTEX COVER

We investigate the fixed parameter complexity of one of the most popular problems in combinatorial optimization, WEIGHTED VERTEX COVER. Given a, graph G = (V, E), a weight function omega : V -->+ R+, and k is an element of R+, WEIGHTED VERTEX COVER (WVC for short) asks for a subset C of vertices in V of weight at most k such that every edge of G has at least one endpoint in C. WVC and its variants have all been shown to be. NP-complete. We show that, when restricting the range of omega to positive integers, the so-called INTEGER-WVC can be solved as fast as unweighted VERTEX COVER. Our main result is that if the range of omega is restricted to positive reals greater than or equal to1, then so-called REAL-WVC can be solved in time O(1.3954(k) + k \V \). If we modify the problem in such a way that k is not the weight of the vertex cover we axe looking for, but the number of vertices in, a minimum weight vertex cover, then the same running time can be obtained. If the weights are arbitrary (referred to by GENERAL-WVC), however, the problem is not fixed parameter tractable unless P = NP.