Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Complexity of the Exact Domatic Number Problem and of the Exact Conveyor
  Flow Shop Problem   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. Our reductions apply Wagner's conditions
sufficient to prove hardness for the levels of the boolean hierarchy over NP.

14
The categories of this paper are: math-ph
5
The categories of this paper are: gr-qc
17
The categories of this paper are: q-fin
4
The categories of this paper are: cond-mat
26
The categories of this paper are: bayes-an
13
The categories of this paper are: quant-ph
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph
20
The categories of this paper are: acc-phys
31
The categories of this paper are: ao-sci
2
The categories of this paper are: math
30
The categories of this paper are: q-alg
37
The categories of this paper are: supr-con