dc.contributor |
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
dc.contributor.author |
Demaine, Erik D. |
dc.contributor.author |
Fomin, Fedor V. |
dc.contributor.author |
Hajiaghayi, Mohammad Taghi |
dc.contributor.author |
Thilikos Touloupas, Dimitrios |
dc.date |
2003-10 |
dc.identifier.citation |
Demaine, E., Fomin, F., Hajiaghayi, M., Thilikos, D. "Bidimensional parameters and local treewidth". 2003. |
dc.identifier.uri |
http://hdl.handle.net/2117/85633 |
dc.language.iso |
eng |
dc.relation |
LSI-03-48-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
dc.subject |
Treewidth |
dc.subject |
Local treewidtf |
dc.subject |
Graph minors |
dc.subject |
Dominating set |
dc.title |
Bidimensional parameters and local treewidth |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
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 F has the parameter-treewidth property for P if there is a function f(p) such that every graph G in F 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 F has the parameter-treewidth property if F 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 F 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. |