Paper by Erik D. Demaine
- 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.
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
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.
- This paper is also available from SIAM.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 5, 2021 by