Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Does the following problem have a name? Is it NP-complete?
Given a multiset of $n$ positive integers, $S$, and an positive integer $m$, does there exist an $m \times n$ matrix whose rows are permutations of $S$ and whose columns all have equal sum?
Example: $S = [1,2,2,3]$, $m=2$. Solution: $$ A = \begin{pmatrix} 1 & 2 & 2 & 3 \\ 3 & 2 & 2 & 1 \end{pmatrix}. $$
This problem is NP hard. Essentially we can reduce from Partition, though there are some issues that mean we can't reduce from Partition directly. Instead, we reduce from a Partition-like problem; this problem can in turn be shown to be NP-complete by a (very slight) variant of the standard Partition NP hardness proof.
In particular, the sum of all elements in the array must be $m \sum_{s\in S} s$. This means that in a solution each column must sum to exactly $\frac{m}{n}\sum_{s\in S} s$. So, if we set $m = n/2$ then each column must sum to $\frac{1}{2}\sum_{s\in S} s$. That leads us to an idea that doesn't quite work. What we'd like to do is start with an even-sized Partition instance $S$, set $m = n/2$, and claim that a solution array exists if and only if there is a solution to Partition. Unfortunately, there are problems. First, the solution must have exactly $n/2$ elements (this is already known to still be NP hard). Second, a column of the matrix might use elements of $S$ multiple times.
Basically, the rest of this post shows that these differences don't make a difference: we define a variant of Partition capturing the above restrictions, and then show that the classic Partition NP-hardness proof almost immediately applies to this variant as well.
Partition variant definition: Let's define a problem called RestrictedPartition, which is a promise version of Partition with some extra restrictions. In RestrictedPartition we are given a set $S$ of positive integers, with the promise that $|S|$ is even and there is no multiset $M$, such that $M$ is not a set, consisting of $n/2$ elements of $S$ such that $\sum_{m\in M} = \frac{1}{2}\sum_{s\in S} s$. (In particular, $S$ must satisfy that if there is a set of $n$ nonnegative integers $c_1\ldots c_n$ such that $\sum_{i=1}^n c_i s_i = \frac{1}{2}\sum_{s\in S} s$, then every $c_i$ must be $1$ or $0$.) Under this restriction, RestrictedPartition asks to determine if there is a subset $S'\subset S$ with $|S'| = n/2$ such that $\sum_{s'\in S'} s' = \frac{1}{2} \sum_{s\in S} s$.
Problem is NP hard reducing from RestrictedPartition If $S$ is an instance of RestrictedPartition, the reduction is to create an instance of this problem with the same $S$ and with $m = n/2$.
If ResitrictedPartition has a solution $S'$ (of size $n/2$), we want too show that there is a solution to this problem. We can set the first column of the final matrix to be $S'$ in sorted order; the next $n/2-1$ columns are each constructed by rotating the previous column down one element. The final $n/2$ columns can be made the same way with $S\setminus S'$. All columns have the same sum, and all rows must have both all elements of $S'$ and all elements of $S\setminus S'$.
For the other direction, we want to show that if this problem has a solution matrix $M$, RestrictedPartition has a solution $S'$. Set $S'$ to be the first column of $M$. We must have $\sum_{s'\in S'} s' = \frac{1}{2}\sum_{s\in S} s$ (shown above) and $|S'| = n/2$. By the assumption on $S$ in RestrictedPartition, all entries in the first column of $M$ must be unique, so $S'$ is a set and we are done.
RestrictedPartition is NP hard reducing from 3 dimensional matching This is basically the classic NP hardness proof for Subset Sum (specifically, the one on wikipedia or in these lecture notes)---basically, we can just observe that the classic reduction already satisfies the multiset promise. Then, we can make a classic change to convert into a Partition instance from a Subset Sum instance, and finally add extra elements to guarantee that there exists a solution with $|S'| = n/2$.
We'll begin by creating a set $S_1$ and a target $T$ that is essentially an instance of subset sum with the additional promise that no multiset is a solution. Then, we'll use $S_1$ and $T$ to create an instance $S$ of RestrictedPartition.
(The next three paragraphs are just the classic subset sum hardness proof) 3DM consists of a set of $m$ edges $E$; each edge is a triple $(x,y,z)$ with $x,y,z\in \{1,\ldots, n\}$. 3DM asks if there is a subset $E'\subseteq E$ such that for any $i\in \{1,\ldots, n\}$, there is exactly one $e'\in E$ such that $i$ is in the first position in $e'$, one $e''\in E$ such that $i$ is in the second position in $e''$, and one $e'''\in E$ such that $i$ is in the third position in $e'''$. ($e'$, $e''$, and $e'''$ need not be distinct.)
For each $e_i\in E$ we create a binary integer $n_i$. We use three helper functions, each of which gives a binary number: $x(i) = 10^{n*i + 4n^2}$; $y(i) = 10^{n*i + 2n^2}$; $z(i) = 10^{n*i}$. If $e_i = (x_i, y_i, z_i)$, then $n_i = x(x_i) + y(y_i) + z(z_i)$. We set $S_1 = \bigcup n_i$. Finally, the target integer $T = \sum_{i = 1}^n x(i) + y(i) + z(i)$.
We're immediately done. If there is a $E'\subseteq E$ that is a solution to the 3DM instance, there is a subset of $S_1$ that sums to $T$ (each entry contributes exactly 3 of the set bits of $T$). Furthermore, no multiset of at most $n$ elements from $S_1$ can sum to $T$ unless that subset corresponds to such an $E'$ because each set bit is $n$ away from any other set bit in all numbers in $S_1$. This is because carries don't matter: $T$ has (for example) a set bit in position $p = n\cdot x_i + 4n^2$ due to $x_i$, and no other set bits in positions ${p - n/2\ldots, p + n/2}$. Every element in $S_1$ also has no set bits in positions ${p - n/2\ldots p-1}\cup {p_1,\ldots p+n/2}$, so if a (multi)subset of $S_1$ of cardinality at most $n/2$ sums to $T$, it must have exactly one entry with $x_i$ set. Applying the same argument to each $y_i$ and $z_i$, we are done.
(Now we reduce from Subset Sum to RestrictedPartition.) We then add to $S_1$ two elements $z_1 = \sum_{s_1\in S_1} s_1$ and $z_2 = T$ to obtain $S_2 = S_1\cup \{z_1\} \cup \{z_2\}$. $S_2$ has a Partition solution if and only if a subset of $S_1$ sums to $T$ (this is the classic Partition proof; again see wikipedia).
Finally, we need to guarantee that a solution has size exactly $|S|/2$---note that the standard technique of adding $0$s to $S_2$ doesn't work since we need all numbers to be positive. Instead we create $|S_2|$ sets of three binary numbers: $M_i = \{m^1_i, m^2_i, m^3_i\}$ for $i = 1, \ldots, |S_2|$, where $m^1_i = 10^{i*n^2 + n^5}$, $m^2_i = 100^{i*n^2 + n^5}$, $m^3_i = 110^{i*n^2 + n^5}$. In particular, for all $i$, $m^1_i + m^2_i = m_3^i$. We define $M = \bigcup M_i$ and $S = S_2 \cup M$. Since all numbers in $M$ are much bigger than any number in $S_2$, any partition $S'$ of $S$ must have, for all $i$, either: (1) both $m^1_i$ and $m^2_i$, but not $m^3_i$, or (2) only $m^3_i$, but not $m^2_i$ or $m^1_i$ (this is essentially the same argument we used in the 3DM reduction: the bits are so spaced apart that the only (multi) subset of $S$ that can account for the set bits in $m^3_i$ are from $m^2_i$ and $m^1_i$). Note that $S$ has size $|S_2| + 3|S_2|$ which is even.
So, if $S_2$ has a partition $S''$, then $S$ has a partition of size $|S|/2$: $M' = m^1_1\cup m^2_1 \cup m^1_2 \cup m^2_2 \ldots \cup m^1_{|S_2| - |S''|} \cup m^2_{|S_2| - |S''|}$ and $M'' = m^3_{|S_2|- |S''| + 1} \cup \ldots \cup m^3_{|S_2|}$; then $S''\cup M' \cup M''$ is a partition of $S$ of size $|S''| + 2(|S_2| - |S''|) + |S''| = 2|S_2| = |S|/2$. For the other direction, if $S$ has a partition $S'$, then $S' \cap S_2$ must be a partition of $S_2$ (by the above argument that if $m^3_i$ is in $S''$ then $m^2_i$ and $m^1_i$ are in $S_2\setminus S''$, and vice versa). Then we are done.
