Vector Domination in split-indifference graphs

Given a graph G=(V,E) and a vector of nonnegative integers R[u]u∈V (the vertex requirements), a set S⊆V is an R-dominating set of G if each u∈V∖S has at least R[u] neighbors in S. The Vector Domination problem aims at finding a minimum R-dominating set S. In this work we describe an O(n)-time algorithm to solve Vector Domination in split-indifference graphs.