Abstract
The so called (σ,ρ)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set S of vertices of a graph G is called (σ,ρ)-dominating if for every vertex v ∈ S, |S ∩ N(v)| ∈ σ, and for every v ∉ S, |S ∩ N(v)| ∈ ρ, where σ and ρ are sets of nonnegative integers and N(v) denotes the open neighborhood of the vertex v in G.) It was known that for any two nonempty finite sets σ and ρ (such that 0 ∉ ρ), the decision problem whether an input graph contains a (σ,ρ)-dominating set is NP-complete, but that when restricted to chordal graphs, some polynomial time solvable instances occur. We show that for chordal graphs, the problem performs a complete dichotomy: it is polynomial time solvable if σ, ρ are such that every chordal graph contains at most one (σ,ρ)-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs (σ,ρ) by a structural description, but at least we can provide a recursive algorithm for their recognition. If ρ contains the 0 element, every graph contains a (σ,ρ)-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-(σ,ρ)-domination problem is NP-complete for chordal graphs whenever ρ contains, besides 0, at least one more integer.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique tree. In: George, J.A., Gilbert, J.R., Liu, J.W.H. (eds.) Sparse Matrix Computation: Graph Theory Issues and Algorithms. IMA Volumes in Mathematics and its Applications, vol. 56, pp. 1–30. Springer, Heidelberg (1993)
Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720–742 (2005)
Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory 42, 61–80 (2003)
Feder, T., Vardi, M.Y.: The computational structure of momotone monadic SNP and constraint satisfaction: A sudy through datalog and group theory. SIAM Journal of Computing 1, 57–104 (1998)
Fiala, J., Kratochvil, J.: Locally injective graph homomorphism: Lists guarantee dichotomy. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 15–26. Springer, Heidelberg (2006)
Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoretical Computer Science 1 349, 67–81 (2005)
Garey, M., Johnson, D.: Computers and intractability. W.H.Freeman, New York (1979)
Haynes, T., Hedetniemi, S., Slater, P.: Domination in Graphs: The Theory. Marcel Dekker, New York (1997)
Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nordic J. Comput. 5, 173–195 (1998)
Hell, P., Nešetřil, J.: On the complexity of H-colouring. Journal of Combinatorial Theory B 48, 92–110 (1990)
Kratochvíl, J., Manuel, P., Miller, M.: Generalized domination in chordal graphs. Nordic Journal of Computing 2, 41–50 (1995)
Proskurowski, A., Telle, J.A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10, 529–550 (1997)
Schaefer, T.J.: The complexity of the satisfability problem. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216–226. ACM Press, New York (1978)
Telle, J.A.: Complexity of domination-type problems in graphs. Nordic Journal of Computing 1, 157–171 (1994)
Telle, J.A.: Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees, PhD tesisis, Department of Computer Science, Universiy of Oregon, Eugene (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golovach, P., Kratochvíl, J. (2007). Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2007. Lecture Notes in Computer Science, vol 4769. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74839-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-74839-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74838-0
Online ISBN: 978-3-540-74839-7
eBook Packages: Computer ScienceComputer Science (R0)