AbstractWe discuss the computational complexity of generalized domination problems, which were introduced in [J. A. Telle: Complexity of domination-type problems in graphs, Nordic Journal of Computing 1 (1994), 157-171], restricted to chordal and interval graphs. The existence problem, parametrized by two sets of nonnegative integers sigma and rho, asks for the existence of a set S of vertices of a given graph such that for every vertex u in S (or u not in S), the number of neighbors of u which are in S is in sigma (in rho, respectively). Telle proved that this problem is NP-complete for general graphs, provided both sigma and rho are finite and 0 not in rho. One of our main results shows that in such cases, the existence problem is polynomially solvable for interval graphs. On the other hand, for chordal graphs, the complexity of the existence problem varies significantly even when sigma and rho contain one element each.
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: chordal graph, interval graph, domination, computational complexity
Selected references
- Jan Arne Telle. Complexity of domination-type problems in graphs. Nordic Journal of Computing, 1(1):157-171, Spring 1994.