NP tells the tale: Vašek Chvátal is a hero

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 $\mathrm{NP}$-hard.

In GRAPH KERNEL problem, we are given a digraph $G=(V,A)$ and are asked whether $G$ has a kernel.

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

As mentioned above, GRAPH KERNEL is $\mathrm{NP}$-hard.

Our problem which we are going to add to the arsenal of $\mathrm{NP}$-complete problems, is called SET MATRIX.

In SET MATRIX, we are given a universe set $U=\{1,2,\dots,n\}$ containing $n$ elements, and $A_{ij}\subseteq U$ for $i,j\in U$ is a matrix each cell of which is a set. We need to decide whether there exist a strict subset $T\subset U$ such that for all $j\not\in T$, there exists $i\in T$ for which $T\subseteq A_{ij}$.

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

THEOREMGRAPH KERNEL $\leq_p$ SET MATRIX

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

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

Now, to ensure $T$ is an independent set in this digraph. For each arc-element $a=(u,v)$, set $A[u,a]=V\setminus\{v\}$ and $A[v,a]=V\setminus\{u\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A[w,a]=V\setminus\{u,v\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A[u,v]=V$

All the other entries of $A$ are set to $\emptyset$.$\square$