Branch and Recharge: Exact Algorithms for Generalized Domination

Abstract

Let σ and $\varrho$ be two sets of nonnegative integers. A vertex subset S ⊆ V of an undirected graph G = (V,E) is called a $(\sigma,\varrho)$-dominating set of G if |N(v) ∩ S| ∈ σ for all v ∈ S and $|N(v)\cap S| \in \varrho$ for all v ∈ V ∖ S. This notion introduced by Telle generalizes many domination-type graph invariants. For many particular choices of σ and $\varrho$ it is NP-complete to decide whether an input graph has a $(\sigma,\varrho)$-dominating set.

We show a general algorithm enumerating all $(\sigma,\varrho)$-dominating sets of an input graph G in time O ^*(c ⁿ) for some c < 2 using only polynomial space, if σ is successor-free, i.e., it does not contain two consecutive integers, and either both σ and $\varrho$ are finite, or one of them is finite and $\sigma \cap \varrho = \emptyset$. Thus in this case one can find maximum and minimum $(\sigma,\varrho)$-dominating sets in time o(2ⁿ). Our algorithm straightforwardly implies a non trivial upper bound c ⁿ with c < 2 for the number of $(\sigma,\varrho)$-dominating sets in an n-vertex graph under the above conditions on σ and $\varrho$.

Finally, we also present algorithms to find maximum and minimum ({p}, {q})-dominating sets and to count the ({p},{q})-dominating sets of a graph in time O ^*(2^n/2).

Part of the research was done when some of the authors were visiting DIMATIA, Prague, in April 2006.