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.

BibTeX

@Article{Bidimensional_SIDMA,
  AUTHOR        = {Erik D. Demaine and Fedor V. Fomin and
                   MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos},
  TITLE         = {Bidimensional Parameters and Local Treewidth},
  JOURNAL       = {SIAM Journal on Discrete Mathematics},
  journalurl    = {http://www.siam.org/journals/sidma/sidma.htm},
  VOLUME        = 18,
  NUMBER        = 3,
  PAGES         = {501--511},
  YEAR          = 2004,

  doi           = {https://dx.doi.org/10.1137/S0895480103433410},
  dblp          = {https://dblp.org/rec/journals/siamdm/DemaineFHT04},
  COMMENTS      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-540-24698-5_15">SpringerLink</A>.},
  PAPERS        = {Bidimensional_LATIN2004},
  replaces      = {Bidimensional_LATIN2004},
  withstudent   = 1,
}

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 SpringerLink.

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)