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 .