## Independent sets with domination constraints

Magnús M. Halldórsson

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

AND University of Bergen

Jan Kratochvíl

Charles University, Czech Republic.

Jan Arne Telle

Department of Computer Science, University of Bergen, Bergen, Norway.

A \rho-independent set S in a graph is parameterized by a set $\rho$
of natural numbers that constrains how the independent set S can dominate
the remaining vertices ($\forall v \not\in S: |N(v) \cap S| \in \rho$.)
For all values of $\rho$, we classify as either NP-complete or polynomial-time
solvable the problems of deciding if a given graph has a \rho-independent
set. We complement this with approximation algorithms and inapproximability
results, for all the corresponding optimization problems.

These approximation results extend also to several related independence
problems. In particular, we obtain a $\sqrt{m}$ approximation of the Set
Packing problem, where $m$ is the number of base elements, as well as a
$\sqrt{n}$ approximation of the maximum independent set in the power graphs
$G^{t}$, for $t$ even.

(Nov 28, 1997)