dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Lokshtanov, Daniel | |
dc.contributor.author | Saurabh, Saket | |
dc.contributor.author | Thilikos, Dimitrios | |
dc.date.accessioned | 2021-05-19T08:00:43Z | |
dc.date.available | 2021-05-19T08:00:43Z | |
dc.date.created | 2021-01-12T16:08:29Z | |
dc.date.issued | 2020 | |
dc.Published | SIAM journal on computing (Print). 2020, 49 1397-1422. | |
dc.identifier.issn | 0097-5397 | |
dc.identifier.uri | https://hdl.handle.net/11250/2755579 | |
dc.description.abstract | Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential 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, Philadelphia, 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 (resp., 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 (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | SIAM | en_US |
dc.title | Bidimensionality and Kernels | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2020 Society for Industrial and Applied Mathematics | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 2 | |
dc.identifier.doi | 10.1137/16M1080264 | |
dc.identifier.cristin | 1870038 | |
dc.source.journal | SIAM journal on computing (Print) | en_US |
dc.source.40 | 49 | |
dc.source.pagenumber | 1397-1422 | en_US |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | SIAM journal on computing (Print). 2020, 49(6), 1397–1422 | en_US |
dc.source.volume | 49 | en_US |
dc.source.issue | 6 | en_US |