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)