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/2001
Entry Accepted: 05/21/2001
Entry Last Modified: 05/21/2001

Modify/Update this entry