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-neighbour in $S$. We show that there exists an $O(3^{\delta \sqrt{k}} n)$~% \footnote{Throughout this paper the constants $\delta$ and $c$ are the same as the comparative constants mentioned in~\cite{kn:alber}.} algorithm to check if a planar digraph has a kernel with at most $k$ vertices. We found a reduction which allows us to separate the sub-exponential part additively from the digraph size. Our result implies an algorithm that checks for a kernel with at most $k$ vertices in time $O(3^{\delta^{\prime} \sqrt{k}} +n)$ for any constant $\delta^{\prime} > \delta$. For plane digraphs we introduce a new parameter which we call the kernel number. For a plane digraph the kernel number is the minimum number of faces to be deleted (i.e., the vertices of the boundary) such that the remaining digraph has a kernel. We show that determining whether the kernel number is at most some constant $k$ is NP-complete for every $k\geq 0$.

Article

Download

View PDF