On Vertex Cover with Fractional Fan-Out Bound

In this paper, we consider a new variant of the minimum weight vertex cover problem (MWVC) in which each vertex can cover a fractional amount of edges incident on it. For example, if the degree of a vertex is five and the designated fraction is 2/3, then it can cover at most ? (2/3) × 5 ? = 4 edges among five incident edges. This problem is motivated by a sustainable monitoring of the environment by a set of agents placed at the vertices of graph G so that the failure of agents can be easily recovered by its nearby agents within a short time. This paper investigates the computational complexity of this optimization problem. More specifically, we show that the number of vertices of odd degree, denoted as no, plays a key role in determining the hardness of the problem, so that when the given fraction is 1/2, the complexity of the problem increases as no increases, i.e., It can be solved in polynomial time when no = O (1), although it cannot be approximated within an arbitrary constant factor when no = n, where n is the total number of vertices in the given graph.