<p><em>EDIT: Added an answer meeting the unique-sum requirement.</em></p>
<p><strong>Lemma 1.</strong> <em>The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.</em></p>
<p><em>Proof.</em> Here's the reduction.  First we describe the reduction to the problem without the requirement that the maximum is unique.</p>
<p>Fix a 3-CNF-SAT instance <span class="math-container">$\phi$</span>.  Assume WLOG that <span class="math-container">$\phi$</span> has more clauses than variables (if not, just duplicate clauses to make it so).  Let <span class="math-container">$n$</span> be the number of clauses.</p>
<p>The reduction outputs a <span class="math-container">$kn\times kn$</span> matrix <span class="math-container">$M$</span>, where <span class="math-container">$k=3$</span>.  <span class="math-container">$M$</span> will be a 0/1 matrix, and will have an <span class="math-container">$n\times n$</span> submatrix of the desired form and having (at least) <span class="math-container">$n$</span> ones iff <span class="math-container">$\phi$</span> is satisfiable.</p>
<p>Create <span class="math-container">$M$</span> as follows. For each variable <span class="math-container">$x$</span> in <span class="math-container">$\phi$</span>, create a window of three columns: a column <span class="math-container">$c(x)$</span> for the literal <span class="math-container">$x$</span>, a column <span class="math-container">$c(\bar x)$</span> for the literal <span class="math-container">$\bar x$</span>, 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 <span class="math-container">$n$</span>.</p>
<p>For each clause, say <span class="math-container">$C=\ell_1\vee \ell_2 \vee \ell_3$</span>, create a window of three rows, one for each literal. Name the three rows, respectively, <span class="math-container">$r(C, \ell_1)$</span>, <span class="math-container">$r(C, \ell_2)$</span>, and <span class="math-container">$r(C, \ell_3)$</span>.  In each row, make just one entry 1: for row <span class="math-container">$r(C, \ell_1)$</span> the entry in column <span class="math-container">$c(\ell_1)$</span>, for row <span class="math-container">$r(C, \ell_2)$</span> the entry in column <span class="math-container">$c(\ell_2)$</span>, and for row <span class="math-container">$r(C, \ell_3)$</span> the entry in column <span class="math-container">$c(\ell_3)$</span>.  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) <span class="math-container">$n$</span> ones if and only if <span class="math-container">$\phi$</span> is satisfiable.</p>
<p>First, suppose that <span class="math-container">$\phi$</span> has a satisfying assignment <span class="math-container">$A$</span>.  Choose the submatrix of <span class="math-container">$M$</span> as follows.  Use the columns corresponding to literals that <span class="math-container">$A$</span> makes true (one for each variable), and one (all-zero) column from each padding column-window.  For each clause <span class="math-container">$C$</span>, choose a literal <span class="math-container">$\ell_i$</span> in <span class="math-container">$C$</span> that <span class="math-container">$A$</span> makes true, and choose the row <span class="math-container">$r(C, \ell_i)$</span> in <span class="math-container">$C$</span>'s row-window.  This defines the <span class="math-container">$n\times n$</span> submatrix.  Each of its rows has a 1, so the total number of 1's in the submatrix is <span class="math-container">$n$</span>.</p>
<p>Conversely, suppose that <span class="math-container">$M$</span> has a submatrix <span class="math-container">$M'$</span> of the desired form with at least <span class="math-container">$n$</span> ones.  For each variable <span class="math-container">$x$</span>, <span class="math-container">$M'$</span> uses either the column for the literal <span class="math-container">$x$</span>, the column for the literal <span class="math-container">$\bar x$</span>, or the dummy column in <span class="math-container">$x$</span>'s column-window.  If <span class="math-container">$M'$</span> uses one of the two literal columns, assign <span class="math-container">$x$</span> the value that makes the literal true.  Otherwise assign <span class="math-container">$x$</span> arbitrarily.  This defines the assignment.</p>
<p>To see that it must be a satisfying assignment, recall that the submatrix has <span class="math-container">$n$</span> rows, and each row of <span class="math-container">$M$</span> has at most one 1, so reach row of the submatrix <span class="math-container">$M'$</span> must have exactly one 1.   By the construction of the row-windows in <span class="math-container">$M$</span>, then, for each clause <span class="math-container">$C=\ell_1\vee \ell_2 \vee \ell_3$</span>, there is a row <span class="math-container">$r(C, \ell_i)$</span> in the submatrix that has a 1, necessarily in the entry for row <span class="math-container">$\ell_i$</span> (as this is the only 1 entry in that row).  So column <span class="math-container">$\ell_i$</span> must be in the submatrix, so the assignment must make <span class="math-container">$\ell_i$</span> true.</p>
<p><em>EDIT: added the part below to handle the unique-sum requirement.</em></p>
<p>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 <span class="math-container">$M^*$</span> obtained from <span class="math-container">$M$</span> by adding a small perturbation to each entry, specifically, such that
<span class="math-container">$$M^*_{ij} = M_{ij} + \epsilon_{ij} \text{ where } \epsilon_{ij}=1/2^{nki + j+1}.$$</span>
Because <span class="math-container">$M$</span> is a 0/1 matrix, the sum of the values in any sub matrix of <span class="math-container">$M$</span> is an integer. Also, for any sub matrix <span class="math-container">$M'$</span> of <span class="math-container">$M^*$</span>, the sum of the perturbations <span class="math-container">$\sum_{ij\in M'} \epsilon_{ij}$</span> is less than 1 and is unique (as it uniquely identifies the set of indices of entries in <span class="math-container">$M'$</span>).  It follows that the valid submatrix of <span class="math-container">$M^*$</span> with maximum sum is unique, and has sum at least <span class="math-container">$n$</span> iff the given 3-CNF-SAT instance <span class="math-container">$\phi$</span> is satisfiable.</p>
<p>(And note that the size of the encoding of <span class="math-container">$M^*$</span> is still polynomial in the size of <span class="math-container">$\phi$</span>.)
<span class="math-container">$~~\Box$</span></p>
<p>Exhaustive search takes time polynomial in <span class="math-container">$k^n$</span>, which is polynomial in the input size in the case that <span class="math-container">$n$</span> is constant (but <span class="math-container">$k$</span> grows).  So that case (fixed <span class="math-container">$n$</span>) has a poly-time algorithm.</p>
<p>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 <span class="math-container">$\phi$</span> is satisfiable, and zero or negative otherwise, so approximating within any factor is NP-hard).</p>

CC BY-SA 4.0
2020-07-03T02:33:43.567Z
I thought it was np complete. If we have only one unique maximum can't we use linear programming techniques to find it?
Turbo
CC BY-SA 4.0
2020-07-03T13:02:07.120Z
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.
Neal Young
CC BY-SA 4.0
2020-07-03T16:55:19.473Z
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?
Turbo
CC BY-SA 4.0
2020-07-03T20:28:05.653Z
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.
Neal Young
CC BY-SA 4.0
2020-07-03T20:32:22.063Z
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.
Neal Young
CC BY-SA 4.0
2020-07-04T00:48:56.417Z
Can polytope with vertex points $0/1$ and having rank $1$ structure be captured by a polynomial sized program?
Turbo
CC BY-SA 4.0
2020-07-04T12:44:04.990Z
What do you mean by a "polytope with rank 1 structure"?  P.s. in my comment above I should have defined $\epsilon_{ij} = 1/2^{n*k*(i+4) + j}$.
Neal Young
CC BY-SA 4.0
2020-07-05T02:09:11.440Z
Take the subset of $\{0,1\}$ cube in $(kn)^2$ dimensions with vertices having exactly $n^2$ many $1$s with the structure that the $1$s form a rank $1$ structure and the number of $1$s in each $k\times k$ block is $1$.
Turbo
CC BY-SA 4.0
2020-07-05T14:49:22.277Z
I don't know if there is a poly-size representation (or poly-time separation oracle) for that polytope.  Also I don't see how, if there is, it would help you solve your problem even in the case that the solution is unique, as your problem asks for a submatrix of $M$, not necessarily of rank 1, and satisfying certain side constraints (e.g. each row-window has one row, each column-window has one column).
Neal Young
CC BY-SA 4.0
2020-07-06T12:48:33.727Z
Ok, well, all I can say with confidence is that the problem in the post is NP-complete, and remains so even if the maximum is required to be unique.  I've edited my answer to give the details of the proof for that case as well.
Neal Young
CC BY-SA 4.0
2020-07-06T20:51:20.793Z
Doesn't the same reduction work?  The max sub-matrix sum for $M$ should be the max number of clauses that can be satisfied in $\phi$.  Am I missing something?
Neal Young
CC BY-SA 4.0
2020-07-07T02:38:14.567Z
Just one clarification. Are you doing some kind of reduction from $NP$ to $UP$? I know $UP\subseteq NP$ but here it seems other way around.
Turbo
CC BY-SA 4.0
2020-07-07T12:46:42.110Z
The reduction is a poly-time reduction from the standard NP-complete problem 3CNF-SAT (with no assumption that there is at most one satisfying assignment), to an instance of your problem that is guaranteed to have a unique maximum.  The reduction produces an instance of your problem in the form of a decision problem, asking whether there is a sub matrix with sum $\ge n$.  Although  the max is guaranteed to be unique (as requested), there could be more than one submatrix with sum $\ge n$. Or, the reduction can be from [MAX-3-SAT](https://en.wikipedia.org/wiki/MAX-3SAT), complete for MAX-SNP.
Neal Young
CC BY-SA 4.0
2020-07-08T01:46:19.150Z
Aren't you making the problem have an unique maximum? That seems to be a reduction to $UP$.
Turbo
CC BY-SA 4.0
2020-07-08T02:19:48.537Z
No, per my previous comment, there can be more than one valid submatrix with sum at least the decision threshold $n$.  (So the obvious non-deterministic TM can have multiple accepting paths.)  Still, there will be only one valid submatrix that attains the maximum value (over all valid submatrices), as you requested.
Neal Young
CC BY-SA 4.0
2020-07-08T03:07:04.487Z
Oh even if there is only one unique submatrix that does not mean only one path will be selected from the NDTM?
Turbo
CC BY-SA 4.0
2020-07-08T03:09:36.493Z
Yes, that's right.
Neal Young
CC BY-SA 4.0
2020-07-08T03:10:50.953Z
That does not make sense unless multiple paths get mapped to the same maximum. If each path is mapped to one submatrix then it should be an Unambiguous TM.
Turbo
CC BY-SA 4.0
2020-07-08T03:11:05.177Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/110327/discussion-between-neal-young-and-t).
Neal Young
CC BY-SA 4.0
2020-07-09T01:39:04.297Z
There is no complete problem for $UP$. Correct?
Turbo
CC BY-SA 4.0
2020-07-03T01:15:37.620Z
2020-07-06T12:52:04.097Z
2020-07-06T12:52:04.097Z
Neal Young
<p>We have a <span class="math-container">$kn\times kn$</span> matrix <span class="math-container">$M$</span> made of <span class="math-container">$n^2$</span> many <span class="math-container">$k\times k$</span> blocks.</p>
<p>We want to find an <span class="math-container">$n\times n$</span> submatrix such that each row and column is from distinct window of size <span class="math-container">$k$</span> such that the sum of entries of sub matrix is maximized.</p>
<ol>
<li><p>What is the complexity of this problem?</p>
</li>
<li><p>What is the complexity of this problem if there is an unique maximum?</p>
</li>
</ol>

CC BY-SA 4.0
2020-07-02T23:17:24.047Z
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?)
Neal Young
CC BY-SA 4.0
2020-07-02T23:18:57.700Z
@NealYoung Yes.
Turbo
<ds.algorithms><linear-algebra>
What is the complexity of this submatrix selection problem?
Turbo
# What is the complexity of this submatrix selection problem?

(Asked by: username_0 on 2020-07-02)

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?

**Tags:** ds.algorithms, linear-algebra
> **Comments:**
> **username_1**: 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?)  
> **username_0**: @NealYoung Yes.  

---

## 1 answers

### Answer by username_1 on 2020-07-03. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: I thought it was np complete. If we have only one unique maximum can't we use linear programming techniques to find it?  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: Can polytope with vertex points $0/1$ and having rank $1$ structure be captured by a polynomial sized program?  
> **username_1**: What do you mean by a "polytope with rank 1 structure"?  P.s. in my comment above I should have defined $\epsilon_{ij} = 1/2^{n*k*(i+4) + j}$.  
> **username_0**: Take the subset of $\{0,1\}$ cube in $(kn)^2$ dimensions with vertices having exactly $n^2$ many $1$s with the structure that the $1$s form a rank $1$ structure and the number of $1$s in each $k\times k$ block is $1$.  
> **username_1**: I don't know if there is a poly-size representation (or poly-time separation oracle) for that polytope.  Also I don't see how, if there is, it would help you solve your problem even in the case that the solution is unique, as your problem asks for a submatrix of $M$, not necessarily of rank 1, and satisfying certain side constraints (e.g. each row-window has one row, each column-window has one column).  
> **username_1**: Ok, well, all I can say with confidence is that the problem in the post is NP-complete, and remains so even if the maximum is required to be unique.  I've edited my answer to give the details of the proof for that case as well.  
> **username_1**: Doesn't the same reduction work?  The max sub-matrix sum for $M$ should be the max number of clauses that can be satisfied in $\phi$.  Am I missing something?  
> **username_0**: Just one clarification. Are you doing some kind of reduction from $NP$ to $UP$? I know $UP\subseteq NP$ but here it seems other way around.  
> **username_1**: The reduction is a poly-time reduction from the standard NP-complete problem 3CNF-SAT (with no assumption that there is at most one satisfying assignment), to an instance of your problem that is guaranteed to have a unique maximum.  The reduction produces an instance of your problem in the form of a decision problem, asking whether there is a sub matrix with sum $\ge n$.  Although  the max is guaranteed to be unique (as requested), there could be more than one submatrix with sum $\ge n$. Or, the reduction can be from [MAX-3-SAT](https://en.wikipedia.org/wiki/MAX-3SAT), complete for MAX-SNP.  
> **username_0**: Aren't you making the problem have an unique maximum? That seems to be a reduction to $UP$.  
> **username_1**: No, per my previous comment, there can be more than one valid submatrix with sum at least the decision threshold $n$.  (So the obvious non-deterministic TM can have multiple accepting paths.)  Still, there will be only one valid submatrix that attains the maximum value (over all valid submatrices), as you requested.  
> **username_0**: Oh even if there is only one unique submatrix that does not mean only one path will be selected from the NDTM?  
> **username_1**: Yes, that's right.  
> **username_0**: That does not make sense unless multiple paths get mapped to the same maximum. If each path is mapped to one submatrix then it should be an Unambiguous TM.  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/110327/discussion-between-neal-young-and-t).  
> **username_0**: There is no complete problem for $UP$. Correct?  

---

