  A kernel of a directed graph is a subset of vertices that is both independent
and absorbing (every vertex not in the kernel has an out-neighbour in the
kernel). Not all directed graphs contain kernels, and computing a kernel or
deciding that none exist is NP-complete even on low-degree planar digraphs. The
existing polynomial-time algorithms for this problem all restrict both the
undirected structure and the edge orientations of the input: for example, to
chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier,
Discrete Appl Math 2020) or to permutation graphs where each clique has a sink
(Abbas and Saoula, 4OR 2005). By contrast, we count the kernels of a fuzzy
circular interval graph in polynomial time, regardless of its edge
orientations, and return a kernel when one exists. (Fuzzy circular graphs were
introduced by Chudnovsky and Seymour in their structure theorem for claw-free
graphs.) We also consider kernels on cographs, where we establish NP-hardness
in general but linear running times on the subclass of threshold graphs.
