Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Bidimensional Parameters and Local Treewidth”, SIAM Journal on Discrete Mathematics, volume 18, number 3, 2004, pages 501–511.

Abstract:

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine the question whether similar bounds can be obtained for larger minor-closed graph classes, and for general families of graph parameters including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family F has the parameter-treewidth property for P if there is an increasing function t such that every graph G ∈ F has treewidth at most t(P(G)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family F has the parameter-treewidth property if F has bounded local treewidth. We also show “if and only if” for some graph parameters, and thus this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families F excluding some fixed graphs have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.

Comments:

This paper is also available from SIAM.

Availability:

The paper is available in PostScript (408k), gzipped PostScript (180k), and PDF (174k).

See information on file formats.

[Google Scholar search]

Related papers:

Bidimensional_LATIN2004 (Bidimensional Parameters and Local Treewidth)