In this paper, we study the {k}-domination, total {k}-domin-ation, {k}-domatic number, and total {k}-domatic number problems, from complexity and algorithmic points of view. Let k ≥ 1 be a fixed integer and ε > 0 be any constant. Under the hardness assumption of $NP\not\subseteq DTIME(n^{O(\log\log n)})$ , we obtain the following results. 1
The total {k}-domination problem is NP-complete even on bipartite graphs.
2
The total {k}-domination problem has a polynomial time ln n approximation algorithm, but cannot be approximated within $(\frac{1}{k}-\epsilon)\ln n$ in polynomial time.
3
The total {k}-domatic number problem has a polynomial time $(\frac{1}{k}+\epsilon)\ln n$ approximation algorithm, but does not have any polynomial time $(\frac{1}{k}-\epsilon)\ln n$ approximation algorithm.
All our results hold also for the non-total variants of the problems.