Kernel in Oriented Biregular Graphs

Abstract

A kernel in a directed graph $D(V,E)$ is a set $S$ of vertices of $D$ such that no two vertices in $S$ are adjacent and for every vertex $u$ in $V\setminus S$, there is a vertex $v$ in $S$ such that $(u,v)$ is an arc of $D$. The problem of existence of a kernel is NP-complete for a general digraph. In this paper, we solve the strong kernel problem of an oriented biregular graph in polynomial time.