ALCOMFT-TR-03-66

Fedor V. Fomin and Dimitrios M. Thilikos
Dominating sets and local treewidth
Barcelona. Work packages 2 and 4. October 2003.

Abstract: It is known that the treewidth of a planar graph with a dominating set of size d is O(\sqrt{d}) and this fact is used as the basis for several fixed parameter algorithms on planar graphs. An interesting question motivating our study is if similar bounds can be obtained for larger minor closed graph families. We say that a graph family \mathcalF has the domination-treewidth property if there is some function f(d) such that every graph G\in\mathcalF with dominating set of size <= d has treewidth <= f(d). We show that a minor-closed graph family \mathcalF has the domination-treewidth property if and only if \mathcalF has bounded local treewidth. This result has important algorithmic consequences.

Postscript file: ALCOMFT-TR-03-66.ps.gz (185 kb).