Περίληψη:
Polynomial time preprocessing to reduce instance size is one of the most
commonly deployed heuristics to tackle computationally hard problems. In
a parameterized problem, every instance I comes with a positive integer
k. The problem is said to admit a polynomial kernel if, in polynomial
time, we can reduce the size of the instance I to a polynomial in k,
while preserving the answer. In this paper, we show that all problems
expressible in Counting Monadic Second Order Logic and satisfying a
compactness property admit a polynomial kernel on graphs of bounded
genus. Our second result is that all problems that have finite integer
index and satisfy a weaker compactness condition admit a linear kernel
on graphs of bounded genus.
The study of kernels on planar graphs was initiated by a seminal paper
of Alber, Fellows, and Niedermeier [J. ACM, 2004] who showed that
PLANAR DOMINATING SET admits a linear kernel. Following this result, a
multitude of problems have been shown to admit linear kernels on planar
graphs by combining the ideas of Alber et al. with problem specific
reduction rules. Our theorems unify and extend all previously known
kernelization results for planar graph problems. Combining our theorems
with the Erdos-Posa property we obtain various new results on linear
kernels for a number of packing and covering problems.
Συγγραφείς:
Bodlaender, Hans L.
Fomin, Fedor V.
Lokshtanov, Daniel and
Penninkx, Eelko
Saurabh, Saket
Thilikos, Dimitrios M.
