Sort and Search: Exact algorithms for generalized domination

In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let σ and ϱ be two sets of non-negative integers. A vertex subset S⊆V of an undirected graph G=(V,E) is called a (σ,ϱ)-dominating set of G if |N(v)∩S|∈σ for all v∈S and |N(v)∩S|∈ϱ for all v∈V∖S. In this paper, we prove that decision, optimization, and counting variants of ({p},{q})-domination are solvable in time 2|V|/2⋅|V|O(1). We also show how to extend these results for infinite and . For the case |σ|+|ϱ|=3, these problems can be solved in time 3|V|/2⋅|V|O(1), and similarly to the case |σ|=|ϱ|=1 it is possible to extend the algorithm for some infinite sets.