TY - JOUR

T1 - Bidimensioiial parameters and local treewidth

AU - Domaine, Erik D.

AU - Fomin, Fedor V.

AU - Hajiaghayi, Mohammad Taghi

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 values 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 parameters including all the parameters where such a 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 a function f(p) such that every graph G ∈ ℱ with parameter at most p has treewidth at most f(p). We prove as our main result that, for a large family of parameters called contraction-bidimensional parameters, a minor-closed graph family ℱ has the parameter-treewidth property if ℱ has bounded local treewidth. We also show "if and only if" for some parameters, and thus this result is in some sense tight. In addition we show that, for a slightly smaller family of parameters called minor-bidimensional parameters, all minor-closed graph families ℱ excluding some fixed graphs have the parameter-treewidth property. The bidimensional parameters include many domination and covering parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, q-dominating set (for fixed q). We use these 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 values 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 parameters including all the parameters where such a 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 a function f(p) such that every graph G ∈ ℱ with parameter at most p has treewidth at most f(p). We prove as our main result that, for a large family of parameters called contraction-bidimensional parameters, a minor-closed graph family ℱ has the parameter-treewidth property if ℱ has bounded local treewidth. We also show "if and only if" for some parameters, and thus this result is in some sense tight. In addition we show that, for a slightly smaller family of parameters called minor-bidimensional parameters, all minor-closed graph families ℱ excluding some fixed graphs have the parameter-treewidth property. The bidimensional parameters include many domination and covering parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, q-dominating set (for fixed q). We use these theorems to develop new fixed-parameter algorithms in these contexts.

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

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

M3 - Article

AN - SCOPUS:23844549219

SN - 0302-9743

VL - 2976

SP - 109

EP - 118

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -