# Solve the K_ELEMENT problem using INTERSECT

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.

• Is $k$ part of the input of K_ELEMENT, or is it fixed? Nov 2 at 6:11
• 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. Nov 2 at 6:13
• @YuvalFilmus $k$ is part of the input. If it weren't I think my first solution would become a polynomial time reduction. Nov 2 at 14:56
• 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
– D.W.
Nov 3 at 17:40