# What is the complexity of this submatrix selection problem?

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.

1. What is the complexity of this problem?

2. What is the complexity of this problem if there is an unique maximum?

• By "distinct window of size $k$" do you mean, one row from rows $1..k$, another row from rows $k+1,..,2k$, etc (one row from each of the rows $i*k+1, i*k_2, .., (i+1)*k$, for $i\in\{0,1,..,n-1\}$? (And same for columns?) Jul 2 '20 at 23:17
• @NealYoung Yes. Jul 2 '20 at 23:18

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).

• I thought it was np complete. If we have only one unique maximum can't we use linear programming techniques to find it? Jul 3 '20 at 2:33
• Generally no, LP doesn't help even if the solution is unique. E.g. UNIQUE-SAT is NP-hard (under randomized reductions), and you can probably do a parsimonious reduction from UNIQUE-SAT to this problem, so the variant when the solution (if there is one) is unique, is still probably NP-hard (at least under randomized reductions). Note that even if the solution is unique, that doesn't mean that the LP relaxation will have an optimal integer solution. The optimal solution might still be fractional. Jul 3 '20 at 13:02
• That information is new to me. I thought if we can set up the set of rank $1$ matrices with $0/1$ entries as a polytope then we can maximize with objective given by vectorized $M$ and then find the unique maximum at a corner point which will be $0/1$. No? Jul 3 '20 at 16:55
• Surely not in general, per my comments above. Or, e.g., take my reduction, and modify $M$ by replacing each $M_{ij}$ entry that equals 1 by a $1+\epsilon_{ij}$, where $\epsilon_{ijj} = (n*k*ii + j)/(nk)^4$. Then the maximum will be unique. So the variant of your problem where you require that the optimum is unique is still NP-hard. Jul 3 '20 at 20:28
• p.s. I'm not sure what LP you have in mind in your comments. I would need more detail to be able to give you any feedback. Jul 3 '20 at 20:32