In a blog post from “Discussions of NP-Complete Problems”, McCulloch describes the **GRAPH KERNEL** problem and link to the note on Chvátal’s personal website which proves that this problem is -hard.

In **GRAPH KERNEL** problem, we are given a digraph and are asked whether has a **kernel**.

A **kernel** of a digraph is a subset of its vertex set which satisfies **(i)** no two vertices of are adjacent, and **(ii)** for every vertex not in there exists an arc from some vertex in pointing to it.

As mentioned above, **GRAPH KERNEL** is -hard.

Our problem which we are going to add to the arsenal of -complete problems, is called **SET MATRIX**.

In **SET MATRIX**, we are given a universe set containing elements, and for is a matrix each cell of which is a set. We need to decide whether there exist a **strict** subset such that for all , there exists for which .

We will reduce **GRAPH KERNEL** to **SET MATRIX **to prove the latter’s hardness.

**THEOREM**: **GRAPH KERNEL** **SET MATRIX**

**PROOF**: For each original vertex, create an element. Call these elements vertex-elements. Denote this set of elements by .

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure is an independent set in this digraph. For each arc-element , set and . Also, just in case none of and is included in , for every , set .

To ensure is a dominating set in a digraph, for each arc set

All the other entries of are set to .