Kernels in planar digraphs

A set S of vertices in a digraph D=(V,A) is a kernel if S is independent and every vertex in V-S has an out-neighbor in S. We show that there exist O(n219.1k+n4)-time and O(k36+219.1kk9+n2)-time algorithms for checking whether a planar digraph D of order n has a kernel with at most k vertices. Moreover, if D has a kernel of size at most k, the algorithms find such a kernel of minimal size.