Exact algorithms for generalized domination

Jan Kratochvil

KAM, MFF UK

Abstract

Let $\sigma$ and $\varrho$ be two sets of nonnegative integers. A vertex subset $S\subseteq V$ of an undirected graph $G=(V,E)$ is called a $(\sigma,\varrho)$-dominating set of $G$ if $|N(v)\cap S| \in \sigma$ for all $v\in S$ and $|N(v)\cap S| \in \varrho$ for all $v\in V\setminus S$. This notion introduced by J. A. Telle generalizes many domination-type graph invariants.

We show a general algorithm enumerating all $(\sigma,\varrho)$-dominating sets of an input graph $G$ in time $O^*(c^n)$ for some $c<2$ using only polynomial space, if $\sigma$ is successor-free, i.e., it does not contain two consecutive integers, and either both $\sigma$ 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 setsin time $o(2^n)$, though for many particular choices of $\sigma$ and $\varrho$ already the