TY - JOUR

T1 - Explicit linear kernels via dyna mic programming

AU - Garnero, Valentin

AU - Paul, Christophe

AU - Sau, Ignasi

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2015 Society for Industrial and Applied Mathematics.

PY - 2015

Y1 - 2015

N2 - Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629-638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503-510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci.,7965(2013), pp. 613-624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-DOMINATING SET and r-SCATTERED SET on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

AB - Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629-638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503-510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci.,7965(2013), pp. 613-624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-DOMINATING SET and r-SCATTERED SET on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

KW - Dynamic programming

KW - Graph minors

KW - Linear kernels

KW - Parameterized complexity

KW - Protrusion replacement

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

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

U2 - 10.1137/140968975

DO - 10.1137/140968975

M3 - Article

AN - SCOPUS:84953275723

SN - 0895-4801

VL - 29

SP - 1864

EP - 1894

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -