Revision #2 Authors: Jörg Rothe, Tobias Riege

Accepted on: 23rd March 2004 00:00

Downloads: 2947

Keywords:

Revision #1 Authors: Tobias Riege, Jörg Rothe

Accepted on: 3rd December 2003 00:00

Downloads: 2886

Keywords:

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.

TR02-068 Authors: Tobias Riege, Jörg Rothe

Publication: 10th December 2002 20:02

Downloads: 3290

Keywords:

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.