A kernel in a directed graph `G` is a set `S` of vertices of `G` such that
• no two vertices in `S` are adjacent and
• for every vertex `u` in `G-S`, there is a vertex `v` in `S` such that `u-->v` is an arc of `G`.
In a technical report On the computational complexity of finding a kernel (Report No. CRM-300, 1973, Centre de recherches mathématiques, Université de Montréal), I have shown that recognizing directed graphs that have a kernel is an NP-complete problem. This easy result is cited in Garey and Johnson and people ask me from time to time for a copy of the report, but I have mislaid or lost it. For this reason, I am going to reproduce the argument here as I recollect it.

The reduction is from `SAT`: given a boolean formula `F` in a conjunctive normal form, we shall construct a directed graph `G` such that `G` has a kernel if and only if `F` is satisfiable. For each clause, say `C`, of `F`, we take three vertices `C1,C2,C3` and join them in the cyclic triangle,

``` C1 --> C2 --> C3 --> C1 ```.
For each variable, say `x`, of `F`, we take two vertices `x` and `¬x` (the negation of `x`) and join them in the cyclic digon
``` x --> ¬x --> x ```.
Finally, for each pair `(v,C)` such that literal `v` appears in clause `C`, we add the three arcs
``` C1 --> v, C2 --> v, C3 --> v ```.
Now a set of vertices of `F` is a kernel if and only if this set consists of literals, includes precisely one of `x` and `¬x` for each variable `x`, and includes at least one literal from each clause of `F`.

An easy variation on this construction produces an oriented graph `G` (meaning a directed graph with no cyclic digons) such that `G` has a kernel if and only if `F` is satisfiable. The trick is to introduce two extra vertices, `x'` and `¬x'`, for each variable `x` of `F` and to replace the digon

``` x --> ¬x --> x ```.
by the directed cycle
``` x --> ¬x --> x' --> ¬x' --> x ```
of length four.