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.


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s