On f-domination: polyhedral and algorithmic results

Given an undirected simple graph G with node set V and edge set E, let f(v), for each node v is an element of V, denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f -dominating set in G is a node subset D such that for each node v is an element of V\D at least f(v) of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f -dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost c(v) is an element of R for each node v is an element of V, find an f -dominating set D in G whose cost, given by Sigma(v is an element of D) c(v), is a minimum.