On f-domination: polyhedral and algorithmic results

Given an undirected simple graph G with node set V and edge set E, let $$f_v$$ f v , for each node $$v \in V$$ v ∈ 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\in V{{\setminus }}D$$ v ∈ V \ D at least $$f_v$$ 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\in {\mathbb {R}}$$ c v ∈ R for each node $$v\in V$$ v ∈ V , find an f-dominating set D in G whose cost, given by $$\sum _{v\in D}{c_v}$$ ∑ v ∈ D c v , is a minimum.