AbstractMany graph parameters are the optimal value of an objective function over selected subsets S of vertices with some constraint on how many selected neighbors vertices in S, and vertices not in S, can have. Classic examples are minimum dominating set and maximum independent set. We give a characterization of these graph parameters that unifies their definitions, facilitates their common algorithmic treatment and allows for their uniform complexity classification. This characterization provides the basis for a taxonomy of domination-type and independence-type problems. We investigate the computational complexity of problems within this taxonomy, identify classes of NP-complete problems and classes of problems solvable in polynomial time.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Selected papers that cite this one
- Pinar Heggernes and Jan Arne Telle. Partitioning Graphs into Generalized Dominating Sets. Nordic Journal of Computing, 5(2):128-142, Summer 1998.
- J. Kratochvíl, P. D. Manuel, and M. Miller. Generalized domination in chordal graphs. Nordic Journal of Computing, 2(1):41-50, Spring 1995.
Selected references
- M. E. Dyer and A. M. Frieze. Planar 3DM is NP-complete. Journal of Algorithms, 7(2):174-184, June 1986.