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(n2^{19.1 \sqrt{k}}+n^4)$-time and $O(2^{19.1 \sqrt{k}} k^9 + n^2)$-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.

Article

Download

View PDF