  


Kernels in planar digraphs
Gregory Gutin (G.Gutinrhul.ac.uk) Abstract: A set $S$ of vertices in a digraph $D=(V,A)$ is a kernel if $S$ is independent and every vertex in $VS$ has an outneighbour 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 subexponential 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 NPcomplete for every $k\geq 0$. Keywords: kernels, digraphs, FTP Category 1: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [Postscript] Entry Submitted: 05/21/2001 Modify/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  