AbstractWe study the computational complexity of partitioning the vertices of a graph into generalized dominating sets. Generalized dominating sets are parameterized by two sets of nonnegative integers sigma and rho which constrain the neighborhood N(v) of vertices. A set S of vertices of a graph is said to be a (sigma, rho)-set if forall v in S: |N(v) intersect S| in sigma and forall v not in S: |N(v) intersect S | in rho. The (k, sigma, rho )-partition problem asks for the existence of a partition V1, V2,...,Vk of vertices of a given graph G such that Vi, i=1,2,...,k is a (sigma, rho)-set of G. We study the computational complexity of this problem as the parameters sigma, rho and k vary.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: graph partitioning, NP-completeness, complexity, domination
Selected references
- Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, November 1981.
- Daniel Leven and Zvi Galil. NP completeness of finding the chromatic index of regular graphs. Journal of Algorithms, 4(1):35-44, March 1983.
- Thomas J. Schaefer. The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pages 216-226, San Diego, California, 1-3 May 1978.
- Jan Arne Telle. Complexity of domination-type problems in graphs. Nordic Journal of Computing, 1(1):157-171, Spring 1994.