Publication at Faculty of Mathematics and Physics |
2007
Abstract
We show that for chordal graphs, the problem of deciding the existence of a ($\sigma,\rho$)-dominating set performs a complete dichotomy: it is polynomial time solvable if $\sigma, \rho$ are such that every chordal graph contains at most one $(\sigma,\rho)$-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs $(\sigma,\rho)$ by a structural description, but at least we can provide a recursive algorithm for their recognition.