A

`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`

.

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`

and
join them in the cyclic triangle,
_{1},C_{2},C_{3}

```
C
```_{1} --> C_{2} --> C_{3} --> C_{1}

.
`x`

, of `F`

, we take two
vertices `x`

and `¬x`

(the negation of
`x`

) and join them in the cyclic digon
```
x --> ¬x --> x
```

.
`(v,C)`

such that literal `v`

appears in clause `C`

, we add the three arcs
```
C
```_{1} --> v,
C_{2} --> v,
C_{3} --> v

.
`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
```

.
```
x --> ¬x --> x' --> ¬x' --> x
```

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