6
$\begingroup$

While dealing with a problem, I uncovered this subproblem:

Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$.

Output: A subset of $S$, $T = \{S_{t_{1}},...,S_{t_{p}}\}$ so that $\mid$ $S_{t_{1}}$ $\cap$ ... $\cap$ $S_{t_{p}}$$\mid$ $\geq k$ with $p=\mid T \mid$ maximized.

I.e. find the greatest number of sets in $S$ whose intersection preserves at least $k$ elements.

Is there any way of solving this problem in reasonable time, say polynomial in $r$ and $n$?

I tried to create an algorithm to solve the problem in reasonable time for large sets and $n$ and got nowhere. There's the obvious brute force algorithm that runs in $n2^r$ time. I also tried to construct a DP algorithm that used smaller subsets for optimal substructure, i.e. making use of $(A \cap B) \cap C = A \cap B \cap C$ and that if $\mid A \cap B \mid < k$, then it's not worth searching any further with $A\cap B$. However, I didn't get anywhere since the number of different subsets grows too quickly.

On the one hand, the problem feels kind of "set coverish" and thus I suspect it's hard. On the other, I'd imagine a problem this simple to be mentioned in some list of hard problems if it were intractable.

$\endgroup$
  • $\begingroup$ I believe that's the maximal bipartite clique problem, or a subset of it, due to specifying k. $\endgroup$ – KWillets Jul 5 '16 at 16:30
  • $\begingroup$ reading the introduction of the paper sciencedirect.com/science/article/pii/S0166218X03003330 it seems that the maximum vertex biclique problem is strongly related to the question, and as the authors state "the problem [the maximum vertex biclique problem] can be solved in polynomial time via the matching algorithm." $\endgroup$ – alecsphys Apr 20 at 10:00
6
$\begingroup$

Here is how to reduce clique to your problem. Given a graph $G = (V,E)$ and a number $\ell$, for each vertex $x$ let $$ S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \neq x\right\} \cup \{ \{x,y\} : \{x,y\} \in E \}. $$ In words, $S_x$ contains all edges in the graph touching $x$, and all edges not touching $x$, whether or not they're in the graph.

One can then show that for every set of vertices $A$, $$ \bigcap_{x \in A} S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \notin A\right\} \cup \{ \{x,y\} : x \in A \text{ and } \{x,y\} \in E \}. $$ In words, the intersection of $S_x$ for $x \in A$ consists of all edges in the graph touching $A$, as well as all edges not touching $A$ (whether in the graph or not). The size of this intersection reaches its maximum $\binom{|V|-|A|}{2} + \binom{|A|}{2}$ if and only if $A$ is a clique in the graph.

Choosing $k = \binom{|V|-\ell}{2} + \binom{\ell}{2}$, the graph contains an $\ell$-clique if and only if there are $p=\ell$ sets whose intersection contains at least $k$ points. The value of $n$ for this instance is $n = \binom{|V|}{2}$.

| cite | improve this answer | |
$\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.