Colloquium Details
Generalized Domination in Special Graph Classes
| Author: | Jan Kratochvil Charles University, Prague |
|---|---|
| Date: | January 27, 2009 |
| Time: | 13:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
We investigate the interplay of polynomial solvability and warranty of unique solvability of a problem under consideration, in the setting of generalized domination.
Given sets sigma and rho of nonnegative integers (as parameters of the problem), a set S of vertices of a graph is called (sigma,rho)-dominating if the number of S-neighbors of any vertex of S (of V-S) is an element of sigma (of rho, respectively). This notion was introduced by Telle and has been investaigated by Telle, Proskurowski, Heggernes, Miller, and others.
In particular, it is known that for any pair of finite nonempty sets sigma and rho (such that rho does not contain 0), already the existence of (sigma, rho)-dominating set in an input graph is NP-complete. We present polynomial/NP-completeness dichotomy results for the cases when the input graphs are chordal or of bounded degeneracy. These results relate to the concept of ambivalence in the following sense.
Given a graph class M, the pair (sigma,rho) is called ambivalent for M if there exists a graph from M which contains at least two different (sigma,rho)-dominating sets; otherwise it is called nonambivalent. For chordal graphs, the existence of a (sigma,rho)-dominating set can be decided in polynomial time when the pair (sigma,rho) is nonambivalent for chordal graphs, and the problem is NP-complete otherwise. Similar results hold for k-degenerate graphs (for every k>1), but - somewhat surprisingly - the proofs are quite different.
The results are a joint work with Petr Golovach from Bergen.
Biography
Jan Kratochvil is a full professor and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. His major area of work is theoretical computer science, in particular algorithms and complexity in graph theory. He received his Ph.D. at Charles University in 1987 for a thesis about domination and codes in graphs.