Paper by Erik D. Demaine
- Erik D. Demaine and MohammadTaghi Hajiaghayi, “Bidimensionality: New Connections between FPT Algorithms and PTASs”, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 590–601.
We demonstrate a new connection between fixed-parameter tractability and
approximation algorithms for combinatorial optimization problems on planar
graphs and their generalizations. Specifically, we extend the theory of
so-called “bidimensional” problems to show that essentially all such
problems have both subexponential fixed-parameter algorithms and PTASs.
Bidimensional problems include e.g. feedback vertex set, vertex cover, minimum
maximal matching, face cover, a series of vertex-removal problems, dominating
set, edge dominating set, r-dominating set, diameter, connected
dominating set, connected edge dominating set, and connected
r-dominating set. We obtain PTASs for all of these problems in planar
graphs and certain generalizations; of particular interest are our results for
the two well-known problems of connected dominating set and general feedback
vertex set for planar graphs and their generalizations, for which PTASs were
not known to exist. Our techniques generalize and in some sense unify the two
main previous approaches for designing PTASs in planar graphs, namely, the
Lipton-Tarjan separator approach [FOCS'77] and the Baker layerwise
decomposition approach [FOCS'83]. In particular, we replace the notion of
separators with a more powerful tool from the bidimensionality theory,
enabling the first approach to apply to a much broader class of minimization
problems than previously possible; and through the use of a structural
backbone and thickening of layers we demonstrate how the second approach can
be applied to problems with a “nonlocal” structure.
- The paper is 12 pages.
- The paper is available in PostScript (449k), gzipped PostScript (166k), and PDF (256k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 4, 2022 by