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
We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks.
We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum of entries of sub matrix is maximized.
What is the complexity of this problem?
What is the complexity of this problem if there is an unique maximum?
EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction. First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$. Assume WLOG that $\phi$ has more clauses than variables (if not, just duplicate clauses to make it so). Let $n$ be the number of clauses.
The reduction outputs a $kn\times kn$ matrix $M$, where $k=3$. $M$ will be a 0/1 matrix, and will have an $n\times n$ submatrix of the desired form and having (at least) $n$ ones iff $\phi$ is satisfiable.
Create $M$ as follows. For each variable $x$ in $\phi$, create a window of three columns: a column $c(x)$ for the literal $x$, a column $c(\bar x)$ for the literal $\bar x$, and one dummy column whose entries are all zero (just so the window has the necessary three columns). Add additional windows of all-zero columns to bring the number of column-windows to the desired number $n$.
For each clause, say $C=\ell_1\vee \ell_2 \vee \ell_3$, create a window of three rows, one for each literal. Name the three rows, respectively, $r(C, \ell_1)$, $r(C, \ell_2)$, and $r(C, \ell_3)$. In each row, make just one entry 1: for row $r(C, \ell_1)$ the entry in column $c(\ell_1)$, for row $r(C, \ell_2)$ the entry in column $c(\ell_2)$, and for row $r(C, \ell_3)$ the entry in column $c(\ell_3)$. Make all other entries zero. This completes the reduction. To finish we observe that there will be a submatrix of the desired form (with a row in each row-window and a column in each column-window) having (at least) $n$ ones if and only if $\phi$ is satisfiable.
First, suppose that $\phi$ has a satisfying assignment $A$. Choose the submatrix of $M$ as follows. Use the columns corresponding to literals that $A$ makes true (one for each variable), and one (all-zero) column from each padding column-window. For each clause $C$, choose a literal $\ell_i$ in $C$ that $A$ makes true, and choose the row $r(C, \ell_i)$ in $C$'s row-window. This defines the $n\times n$ submatrix. Each of its rows has a 1, so the total number of 1's in the submatrix is $n$.
Conversely, suppose that $M$ has a submatrix $M'$ of the desired form with at least $n$ ones. For each variable $x$, $M'$ uses either the column for the literal $x$, the column for the literal $\bar x$, or the dummy column in $x$'s column-window. If $M'$ uses one of the two literal columns, assign $x$ the value that makes the literal true. Otherwise assign $x$ arbitrarily. This defines the assignment.
To see that it must be a satisfying assignment, recall that the submatrix has $n$ rows, and each row of $M$ has at most one 1, so reach row of the submatrix $M'$ must have exactly one 1. By the construction of the row-windows in $M$, then, for each clause $C=\ell_1\vee \ell_2 \vee \ell_3$, there is a row $r(C, \ell_i)$ in the submatrix that has a 1, necessarily in the entry for row $\ell_i$ (as this is the only 1 entry in that row). So column $\ell_i$ must be in the submatrix, so the assignment must make $\ell_i$ true.
EDIT: added the part below to handle the unique-sum requirement.
Hence, the reduction is correct. Finally, to reduce 3CNF-SAT to the problem when the maximum is required to be unique, modify the previous reduction to output the matrix $M^*$ obtained from $M$ by adding a small perturbation to each entry, specifically, such that $$M^*_{ij} = M_{ij} + \epsilon_{ij} \text{ where } \epsilon_{ij}=1/2^{nki + j+1}.$$ Because $M$ is a 0/1 matrix, the sum of the values in any sub matrix of $M$ is an integer. Also, for any sub matrix $M'$ of $M^*$, the sum of the perturbations $\sum_{ij\in M'} \epsilon_{ij}$ is less than 1 and is unique (as it uniquely identifies the set of indices of entries in $M'$). It follows that the valid submatrix of $M^*$ with maximum sum is unique, and has sum at least $n$ iff the given 3-CNF-SAT instance $\phi$ is satisfiable.
(And note that the size of the encoding of $M^*$ is still polynomial in the size of $\phi$.) $~~\Box$
Exhaustive search takes time polynomial in $k^n$, which is polynomial in the input size in the case that $n$ is constant (but $k$ grows). So that case (fixed $n$) has a poly-time algorithm.
One could ask further about, say, hardness of approximation. The above reduction can be done from MAX-3SAT to show that the problem has no PTAS. But to me it looks like the problem generalizes a variant of Bipartite Densest Subgraph, so may be even harder to approximate. (This assumes the matrix has non-negative entries. If negative entries are allowed, it's easy to extend the above reduction so that the optimal value is 1 iff $\phi$ is satisfiable, and zero or negative otherwise, so approximating within any factor is NP-hard).
