Computer Science – Computational Complexity
Scientific paper
2002-12-09
Computer Science
Computational Complexity
37 pages; 4 figures
Scientific paper
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.
Riege Tobias
Rothe Jörg
No associations
LandOfFree
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-488741