We prove that the exact versions of the domatic number problem are
complete for the levels of the boolean hierarchy over NP. The domatic
number problem, which arises in the area of computer networks, is
the problem of partitioning a given graph into a maximum number of
disjoint dominating sets. This number is called the domatic number of
the graph. We prove that the problem of determining whether or not the
domatic number of a given graph is {\em exactly} one of k given values
is complete for the 2k-th level of the boolean hierarchy over NP.
In particular, for k = 1, it is DP-complete to determine whether or not
the domatic number of a given graph equals exactly a given integer.
Note that DP is the second level of the boolean hierarchy over NP.
We obtain similar results for the exact versions of generalized
dominating set problems and of the conveyor flow shop problem, which
arises in real-world applications in the wholesale business, where
warehouses are supplied with goods from a central storehouse. Our
reductions apply Wagner's conditions sufficient to prove hardness for
the levels of the boolean hierarchy over NP.

We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number
problem, which arises in the area of computer networks, is the problem of
partitioning a given graph into a maximum number of disjoint dominating
sets. This number is called the domatic number of the graph. We prove that
the problem of determining whether or not the domatic number of a given
graph is {\em exactly\/} one of k given values is complete for
the 2k-th level of the boolean hierarchy over NP. In
particular, for k = 1, it is DP-complete to determine whether or not the
domatic number of a given graph equals exactly a given integer. Note that
DP is the second level of the boolean hierarchy over NP. We obtain similar
results for the exact versions of
the conveyor flow shop problem, which arises in real-world applications in
the wholesale business, where warehouses are supplied with goods from a
central storehouse. Our reductions apply Wagner's conditions sufficient to
prove hardness for the levels of the boolean hierarchy over NP.