3
$\begingroup$

I'm trying to reduce the following problem to a more well-known formulation.

I have a bunch of subsets $\{S_i \}_{i \in I}$ of some finite set.

I would like to put them into (disjoint) groups $\{ G_j \}_{j \in J}$ such that $\max_{j \in J} \left| \bigcup \{S \in G_j\} \right|$ is as small as possible. The number of groups $|J|$ is a fixed constant $k$.

An example: $k = 2$, $S_1 = \{a, b\}$, $S_2 = \{b, c\}$.

If $G_1 = \{S_1\}$ and $G_2 = \{S_2\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1|, |S_2|\} = 2$$

If instead $G_1 = \{S_1, S_2\}$ and $G_2 = \{\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1 \cup S_2|, |\{\}|\} = 3$$

so the latter grouping is worse than the former.

$\endgroup$
  • $\begingroup$ This problem is NP-hard. You can reduce 3-partition to it. In particular, given an instance $a_1, ..., a_{3n}$, set $k = n$ and let $S_i$ be a set of $a_i$ elements with the sets $\{S_i\}_{i\in I}$ disjoint. Then the maximum which you are minimizing can be made as small as three times the average of the $a_i$s if and only if the 3-partition instance is a yes instance. $\endgroup$ – Mikhail Rudoy Jan 29 '17 at 5:27
  • 3
    $\begingroup$ @MikhailRudoy : ​ "fixed constant $k$" ​ ​ ​ ​ $\endgroup$ – user6973 Jan 29 '17 at 5:47
  • $\begingroup$ How about defining a graph where each set as a vertex and edge weights as number of common elements. Then maybe this can be formulated as a cut-flow problem? $\endgroup$ – padawan Feb 12 '17 at 18:39
2
+50
$\begingroup$

I don't know of a way to reduce your problem to a more well known formulation, but I can prove that your problem is NP-hard:

In particular, consider the decision version in which we ask whether it is possible to make $\max_{j\in J}|\bigcup\{S \in G_j\}|$ less than or equal to some threshold $T$.

I prove below by reduction from clique that this decision problem with $k = 2$ is NP-hard.


First the reduction:


Suppose we are given a graph $G = (V, E)$ with $n$ vertices and $m$ edges and a value $c$. We wish to know whether $G$ has a clique of size $c$. We use $G$ and $c$ to construct an instance of your problem.

Define $t_1 = n + m - {c \choose 2}$ and define $t_2 = {c \choose 2} + c$. Then we set the threshold value $T$ to equal $2t_1 + 2t_2$.

We set the universe of elements $U = \bigcup_{i \in I} S_i$ to equal $$\{a_1, a_2, \ldots, a_{T-t_1}\} \cup \{b_1, b_2, \ldots, b_{T-t_2}\} \cup V \cup E$$.

We create exactly $m + 2$ subsets $S_i$:

  • We define $S_1$ to be $\{a_1, a_2, \ldots, a_{T-t_1}\} \cup V$.
  • We define $S_2$ to be $\{b_1, b_2, \ldots, b_{T-t_2}\}$
  • If $E = \{e_1, e_2, \ldots, e_m\}$, then for $i = 1, \ldots, m$ we define $S_{i+2}$ to be $\{e_i, x, y\}$, where $x$ and $y$ are the two endpoints of $e_i$

Now I'll prove correctness:


There are only two $G_j$s. Note that $S_1$ and $S_2$ cannot be in the same $G_j$ because $|S_1 \cup S_2| = 2T -t_1-t_2+n = T + t_1 + t_2 + n > T$. As a result, the two $G_j$s will contain one of $S_1, S_2$ each. Without loss of generality, suppose $G_1$ contains $S_1$ and $G_2$ contains $S_2$.

Let $E_1$ be the set of edges $e_i$ such that $S_{i+2}$ is in $G_1$ and similarly let $E_2$ be the set of edges $e_i$ such that $S_{i+2}$ is in $G_2$.

Then consider the value $|\bigcup\{S \in G_1\}|$. $G_1$ consists of $S_1$ together with the $S_{i+2}$s for those $i$ for which $e_i \in E_1$. Each $S_{i+2}$ has exactly three elements: two vertices and one edge. But $S_1$ already contains all of the vertices. In other words, we see that the set $\bigcup\{S \in G_1\}$ is equal to $\{a_1, a_2, \ldots, a_{T-t_1}\} \cup V \cup E_1$. Then the size of this set is $(T - t_1) + n + |E_1| = T - (n + m - {c \choose 2}) + n |E_1| = T - (m - {c \choose 2}) + |E_1|$.

Next consider the value $|\bigcup\{S \in G_2\}|$. $G_2$ consists of $S_2$ together with the $S_{i+2}$s for those $i$ for which $e_i \in E_2$. Define $V_2$ to be the set of endpoints of edges in $E_2$. Then the set $\bigcup\{S \in G_2\}$ is equal to $\{b_1, b_2, \ldots, b_{T-t_2}\} \cup E_2 \cup V_2$. The size of this set is $(T -t_2) + |E_2| + |V_2| = (T - {c \choose 2} - c) + |E_2| + |V_2|$.

A partition of edges into $E_1$ and $E_2$ solves this problem if and only if both $T - (m - {c \choose 2}) + |E_1|$ and $(T - {c \choose 2} - c) + |E_2| + |V_2|$ are at most $T$. But $$T - (m - {c \choose 2}) + |E_1| \le T$$ is equivalent to $|E_1| \le (m - {c \choose 2})$, which in turn is equivalent to $|E_2| \ge {c \choose 2}$. Furthermore, $$(T - {c \choose 2} - c) + |E_2| + |V_2| \le T$$ is equivalent to $|E_2| + |V_2| \le c + {c \choose 2}$.

In other words, this problem is solvable if and only if we can choose at least ${c \choose 2}$ edges such that the number of chosen edges plus the total number of vertices incident on those edges is at most $c + {c \choose 2}$. It is possible to choose at least ${c \choose 2}$ edges satisfying this constraint if and only if it is possible to choose exactly ${c \choose 2}$ edges satisfying this constraint (since choosing extra edges can only make it harder to satisfy the constraint). Thus, this problem is solvable if and only if we can choose exactly ${c \choose 2}$ edges such that the number of chosen edges plus the total number of vertices incident on those edges is $c + {c \choose 2}$. In other words, this problem is solvable if and only if we can choose exactly ${c \choose 2}$ edges such that the total number of vertices incident on those edges is at most $c$. This is equivalent to saying that the graph $G$ must have a clique of size $c$. Thus the given reduction is answer preserving.


It is also easy to generalize the above reduction to also show the $k > 2$ case hard. For example, to show $k = 3$ hard, we simply add another set $\{c_1, c_2, \ldots, c_T\}$. Then one of the $G_j$s will be forced to contain this $S_i$ and no other, reducing the rest of the problem to the same situation as above.

$\endgroup$
2
$\begingroup$

The problem is NP-complete already for $k=3$ (and I guess also for $k=2$). We reduce the following problem to it: For an input $r$-regular graph $G$, decide whether $G$ has an equitable $3$-coloring, i.e., one where the size of each color class is the same. (I couldn't find a reference for this, but one can easily reduce the classical $3$-coloring problem to this by adding a few extra vertices and edges.)

The reduction is as follows. For each vertex $v$ of the input graph $G$, define a set $S_v=\{\{u,v\}\mid uv\notin E(G)\}$. For any subset $X$ of the vertices we have

$$|\cup_{\{v\in X\}} S_v|=|X|(n-1-r)-|X_2|$$

where $X_2$ is the set of non-adjacent pairs in $X$. If $|X|\ge n/3$, this is at least

$$\frac{n(n-1-r)}3-\binom{\frac n3}{2}$$

with equality only if $|X|=n/3$ and all pairs in $X$ are non-adjacent. Since in any grouping of the $S_v$ into three groups we have such an $X$, we are done.

$\endgroup$
2
$\begingroup$

Joining the club of NP completeness proofs!

This time with $k = 2$. We reduce from the Minimum Bisection problem. Here input is a graph $G$ on $2n$ vertices and an integer $t$, the task is to determine whether there is a partition of $V(G)$ into two sets $A$ and $B$, each of size $n$, such that no more than $t$ edges go between $A$ and $B$. The problem remains NP-hard on $3$-regular graphs (See T. Bui, S. Chaudhuri, T. Leighton, M. Sipser, Graph bisection algorithms with good average case behavior, Combinatorica 7 (1987) 171–191).

Given a $3$-regular graph $G$ and integer $k$ make an instance of the problem by making a universe U that has $10n$ elements for every vertex in $V(G)$ and one element for every edge in $G$. We make a set for each vertex $v$, the set contains all the $10n$ elements corresponding to $v$, and the $3$ elements corresponding to the edges incident to $v$.

Any grouping into groups where both groups have a union of size at most $10n^2 + 10n$ must put exactly $n$ vertices on each side. Each such balanced grouping corresponds to a bisection $(A, B)$ of $G$, where the size of the union of each group is precisely $10n^2 + 3n/2 + |E(A,B)|$ where $E(A,B)$ is the set of edges with one endpoint in $A$ and the other in $B$. (Each vertex covers 3 edges, each edge is covered twice, but the edges with both endpoints on the same side contribute to the size of the union(s) only once.)

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