Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Bidimensional Parameters and Local Treewidth”, in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 109–118.

BibTeX

@InProceedings{Bidimensional_LATIN2004,
  AUTHOR        = {Erik D. Demaine and Fedor V. Fomin and
                   MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos},
  TITLE         = {Bidimensional Parameters and Local Treewidth},
  BOOKTITLE     = {Proceedings of the 6th Latin American Symposium on
                   Theoretical Informatics (LATIN 2004)},
  bookurl       = {http://www.latintcs.org/2004/},
  ADDRESS       = {Buenos Aires, Argentina},
  MONTH         = {April 5--8},
  YEAR          = {2004},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 2976,
  PAGES         = {109--118},

  doi           = {https://dx.doi.org/10.1007/978-3-540-24698-5_15},
  dblp          = {https://dblp.org/rec/conf/latin/DemaineFHT04},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-540-24698-5_15">SpringerLink</A>.},
  copyright     = {The paper is \copyright Springer-Verlag.},
  length        = {10 pages},
  papers        = {Bidimensional_SIDMA},
  withstudent   = 1,
}

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.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (180k), gzipped PostScript (72k), and PDF (224k).

See information on file formats.

[Google Scholar search]

Related papers:

Bidimensional_SIDMA (Bidimensional Parameters and Local Treewidth)