3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Aug 2 '16 at 10:07
  • $\begingroup$ @Raphael I've added my attempts. Please let me know if this is still not sufficient :) $\endgroup$ – user355066 Aug 2 '16 at 10:36
  • 2
    $\begingroup$ (a) Suppose $\forall i,j . 1 \notin A_{i,j}$. What constraints on $T$ can you encode by choosing $A_{1,1},\dots,A_{n,1}$ appropriately? (b) Suppose $\forall i . A_{i,1} = \emptyset$. What constraints on $T$ does this encode? (c) Can you do anything with this? What class of constraints on $T$ can you encode using these kinds of ideas? Does this give you any ideas? $\endgroup$ – D.W. Aug 2 '16 at 12:16
  • $\begingroup$ @D.W. For (a), we can conclude that $1\not\in T$, since if $1\in T$ we must have $1\not\in A_{i,j}$ for some $i,j$. For (b), we can conclude that $1\in T$, since if $1\not\in T$ we must have $T\subseteq A_{i,1}=\emptyset$. Combining (a) and (b), we have that if both conditions are satisfied, then no subset $T$ exists. I'm not sure what we can conclude from here, though. $\endgroup$ – user355066 Aug 2 '16 at 20:28
  • $\begingroup$ Nope, you haven't thought about (a) enough. Keep working at it. If you choose the $A_{i,1}$ cleverly, you can encode more sophisticated constraints than $1 \notin T$. Also, I'm not suggesting you apply (a) + (b) together to the same column; e.g., you could apply (a) to column 1 and (b) to column 2. Anyway, I've given you a direction. Keep working to see what types of constraints you are able to encode. Then, edit your question to show the full set of constraints you've been able to express in your problem. Then, think about whether this helps you find a reduction (to prove NP-completeness). $\endgroup$ – D.W. Aug 2 '16 at 21:06
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.