# Noon lecture

On 08.03.2007 at 12:20 in S5, there is the following noon lecture:

# Exact algorithms for generalized domination

## 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 existence of a $(\sigma,\varrho)$-dominating set is NP-complete. Our algorithm straightforwardly implies a non trivial upper bound $c^n$ with $c<2$ for the number of $(\sigma,\varrho)$-dominating sets in an $n$-vertex graph under the above conditions on $\sigma$ and $\varrho$.

Based on a joint work with Fedor Fomin, Petr Golovach, Dieter Kratsch and Mathieu Liedloff

Modified: 19. 10. 2010