Optimization Online


Kernels in planar digraphs

Gregory Gutin (G.Gutin***at***rhul.ac.uk)
Ton Kloks (ton***at***cs.rhul.ac.uk)
C.M. Lee (cmlee***at***cs.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 )


Download: [Postscript]

Entry Submitted: 05/21/2001
Entry Accepted: 05/21/2001
Entry Last Modified: 05/21/2001

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society