On the computational complexity of finding a kernel

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 C₁,C₂,C₃ and join them in the cyclic triangle,


C₁ --> C₂ --> C₃ --> C₁

. 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


C₁ --> v,
C₂ --> v,
C₃ --> 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