Menu
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 introduce the acyclic kernel problem of an undirected graph \(G\) and solve it in polynomial time for uniform theta graphs and even quasi-uniform theta graphs.