Computational complexity of generalized domination:: A complete dichotomy for chordal graphs

The so called (alpha, rho)-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 (alpha, rho) - dominating if for every vertex upsilon is an element of S, vertical bar S boolean AND N(upsilon)vertical bar is an element of sigma, and for every upsilon is not an element of S, vertical bar S boolean AND N(upsilon)vertical bar is an element of rho, where sigma and rho are sets of nonnegative integers and N(upsilon) denotes the open neighborhood of the vertex v in G.) It was known that for any two nonempty finite sets sigma and rho (such that 0 is not an element of rho), the decision problem whether an input graph contains a (alpha, rho)-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 alpha, rho are such that every chordal graph contains at most one (alpha, rho)-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs (alpha, rho) by a structural description, but at least we can provide a recursive algorithm for their recognition. If rho contains the 0 element, every graph contains a (alpha, rho)-dominating set (the empty one), and so the nontrivial question here is to ask for a maximum such set. We show that MAX-(alpha, rho)-domination problem is NP-complete for chordal graphs whenever p contains, besides 0, at least one more integer.