2
$\begingroup$

Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N. Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n? I read somewhere (without mentioning why) that it's an NP-complete problem, but I think it can be solved simply by taking the union of all subsets and comparing it to k. If it isn't equal to k, then we can't form a subset R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n. is it an NPC problem or P problem ?

$\endgroup$
1
  • $\begingroup$ Please edit your post to use Mathjax and formatting so it isn't all one big paragraph. See here for a short introduction. $\endgroup$
    – D.W.
    Feb 22 at 20:38

1 Answer 1

2
$\begingroup$

Right, it is in $\text{PTIME}$. The condition $|R\cap S_i| = |S_i|$ is equivalent to $S_i\subseteq R$. So the problem is to find a subset $R$ whose size is $k$ and contains all sets in $\{S_i\}_{i\in [n]}$. In other words, $ \bigcup\limits_{i\in [n]} S_i \subseteq R$. So you can simply find the smallest such set $\bigcup\limits_{i\in [n]} S_i$ and then compare $|\bigcup\limits_{i\in [n]} S_i|$ to $k$. If $|\bigcup\limits_{i\in [n]} S_i| > k$ or $k > |A|$, then there is no such set $R$. Otherwise, there is such a set.

As a conclusion, the problem is not known to be $\text{NP-complete}$, since we do not know yet whether $\text{PTIME} = \text{NP}$.

$\endgroup$
1
  • 2
    $\begingroup$ @Moh, please don't ask new questions in the comments. Instead, you can use the 'Ask Question' button to ask a new question. Make sure to provide full context, make it self-contained, and make it useful for others. $\endgroup$
    – D.W.
    Feb 22 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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