A kernel in a directed graph G is a set S of vertices of G such that 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.

Back to Vašek Chvátal's home page