On total f-domination: Polyhedral and algorithmic results

Given an undirected simple graph G with node set V and edge set E, let fv, for each node 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∈V∖D at least fv 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 cv∈R for each node v∈V, find an f-dominating set D in G whose cost, given by ∑v∈Dcv, is a minimum.

Given a graph G=(V,E) and integer values fv, v∈V, a node subset D⊂V is a total f-dominating set if every node v∈V is adjacent to at least fvnodes of D. Given a weight system c(v), v∈V, the minimum weight total f-dominating set problem is to find a total f-dominating set of minimum total weight. In this article, we propose a polyhedral study of the associated polytope together with a complete and compact description of the polytope for totally unimodular graphs and cycles. We also propose a linear time dynamic programming algorithm for the case of trees.