TY - JOUR

T1 - Bidimensionality and kernels

AU - Fomin, Fedor V.

AU - Lokshtanov, Daniel

AU - Saurabh, Saket

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics Publications. All rights reserved.

PY - 2020/12/18

Y1 - 2020/12/18

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

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

KW - Bidimensionality

KW - Kernelization

KW - Parameterized algorithms

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85099282683&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099282683&partnerID=8YFLogxK

U2 - 10.1137/16M1080264

DO - 10.1137/16M1080264

M3 - Article

AN - SCOPUS:85099282683

SN - 0097-5397

VL - 49

SP - 1397

EP - 1422

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -