- Kernels in planar digraphs Gregory Gutin (G.Gutinrhul.ac.uk) Ton Kloks (toncs.rhul.ac.uk) C.M. Lee (cmleecs.ccu.edu.tw) 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-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$. Keywords: kernels, digraphs, FTP Category 1: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [Postscript]Entry Submitted: 05/21/2001Entry Accepted: 05/21/2001Entry Last Modified: 05/21/2001Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.