Kernels in planar digraphs

Abstract

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 -time and -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.