TY - JOUR

T1 - Bidimensional parameters and local treewidth

AU - Demaine, Erik D.

AU - Fomin, Fedor V.

AU - Hajiaghayi, Mohammadtaghi

AU - Thilikos, Dimitrios M.

PY - 2004

Y1 - 2004

N2 - 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 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 ℱ has the parameter-treewidth property for P if there is an increasing function t such that every graph G ∈ ℱ 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 ℱ has the parameter-treewidth property if ℱ 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 ℱ, 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, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.

AB - 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 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 ℱ has the parameter-treewidth property for P if there is an increasing function t such that every graph G ∈ ℱ 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 ℱ has the parameter-treewidth property if ℱ 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 ℱ, 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, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.

KW - Dominating set

KW - Graph minors

KW - Local treewidth

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=20744459687&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744459687&partnerID=8YFLogxK

U2 - 10.1137/S0895480103433410

DO - 10.1137/S0895480103433410

M3 - Article

AN - SCOPUS:20744459687

SN - 0895-4801

VL - 18

SP - 501

EP - 511

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -