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.