NP-hardness of problem with indices and subsets

Question

Consider the following problem.

Let $S=\{1,2,\dots,n\}$, and $A_{ij}\subseteq S$ for $i,j\in S$. Does there exist a strict subset $T\subset S$ such that for all $j\not\in T$, there exists $i\in T$ for which $T\subseteq A_{ij}$?

(For $T=S$, this is trivially true, so we disallow it.)

The problem is in NP: given a set $T$, it is easy to verify whether it satisfies the property. Is it also NP-hard, or does there exist a polytime algorithm?

I tried to construct such a set $T$ greedily by starting with some $i\in S$. If $i\in A_{ij}$ for all $j\not\in i$, we can choose $T=\{i\}$ and are done. Otherwise, there is some $j$ for which $i\not\in A_{ij}$, so we can try adding $j$ into the set, and iterate on the new set $T=\{ij\}$ until the process stops. The problem is that there is no guarantee that this will stop before $T$ is the whole set $S$ even if such $T\neq S$ exists.

I also thought about dynamic programming, but it's not clear what the subproblems should be in this setting. On the NP-hardness side, I thought about reducing from some problems related to sets. There are problems like subset-sum or partition, but those concern sums of elements and are not directly relevant.

Answer 1

This question shows that Vašek Chvátal is a hero.

Reduce from graph kernel.

In the GRAPH KERNEL problem, the input data is a digraph and the task is to determine whether it 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.

So, we need to transform a digraph to your set matrix problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element 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$.