Bidimensionality and Kernels
From MaRDI portal
Publication:3387764
DOI10.1137/16M1080264zbMATH Open1475.05161arXiv1606.05689OpenAlexW3116379639MaRDI QIDQ3387764
Author name not available (Why is that?)
Publication date: 13 January 2021
Published in: (Search for Journal in Brave)
Abstract: Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work.
Full work available at URL: https://arxiv.org/abs/1606.05689
No records found.
No records found.
This page was built for publication: Bidimensionality and Kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387764)
