Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem |
| |
Authors: | Tobias Riege Jörg Rothe |
| |
Affiliation: | (1) Institut fur Informatik, Heinrich-Heine-Universitat Dusseldorf, 40225 Dusseldorf, Germany |
| |
Abstract: | 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 exactly one of k given values is complete for
BH2k(NP), the 2kth 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 = BH2(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|