Suppose you have a machine that takes inputs a set of sets, $\{S_1,S_2,\dots S_n\}$, and an integer $k$. The machine then returns True if $S_1$ intersects every other set $S_2,\dots,S_n$ in at least one place and otherwise returns False. Call this problem the INTERSECT problem. Now call the K_ELEMENT problem the problem of deciding whether $S_1$ intersects every other set in at least $k$ places. Give a polynomial time reduction of K_ELEMENT to INTERSECT.

I think I know how to give a non-polynomial time reduction. For a given instance $\{S_1,\dots,S_n\}$ and $k$ of the K_ELEMENT problem, we can compute every subset of $S_i$ of size $|S_i|-k+1$ and give $S_1$ together with all of these constructed sets as inputs to the INTERSECT solver. The problem is that as $|S_i|=n_i$ and $k$ grow, the number of subsets this has to generate grows like $\binom{n_i}k$ which is not polynomial.

So how to do this while generating fewer sets? Suppose for simplicity that you just take two sets $S=\{1,2,3,4,5,6\}$ and $T$ any set, and $k=2$. Then we want to know whether some $k$ elements of $T$ are elements of $S$, and we can only do this by making a single call to INTERSECT then ... I just can't see a way of making subsets to do this.

I started wondering whether we should construct sets of sets, but this seemed to run into the same combinatorial explosion.

  • $\begingroup$ Is $k$ part of the input of K_ELEMENT, or is it fixed? $\endgroup$ Nov 2 at 6:11
  • $\begingroup$ The problem K_ELEMENT can be solved in polynomial time, so you can given a polynomial time reduction which solves K_ELEMENT and then outputs either a fixed Yes instance of INTERSECT or a fixed No instance of INTERSECT. $\endgroup$ Nov 2 at 6:13
  • 1
    $\begingroup$ @YuvalFilmus $k$ is part of the input. If it weren't I think my first solution would become a polynomial time reduction. $\endgroup$
    – Addem
    Nov 2 at 14:56
  • $\begingroup$ Where did you encounter this task? Can you credit the source? Note that we require attribution for all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Nov 3 at 17:40

Your Answer

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

Browse other questions tagged or ask your own question.