# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Fixed-Parameter Tractability
If Condition (2) (respectively Condition (3)) is violated, then there are more than \(h_{1}\) (respectively \(h_{2}\)) rows that have to be in row block \(I_{1}\) (respectively \(I_{2}\)). Thus, if \(j\) does not fit into a column block \(J_{s}\), then there is no solution where \(j\in J_{s}\). We now need to find out, for each column, to which fitting column blocks it should be assigned. Intuitively, we now prove that in most cases, a column has at most two fitting column blocks and, in the remaining cases, at most two pairs of \"equivalent\" column blocks. Consider a given column \(j\in[n]\). Write \(a=\min\{a_{ij}\mid i\in[m]\}\) and \(b=\max\{a_{ij}\mid i\in[m]\}\). If \(b\geq a+3\), then Condition (1) is always violated: \(j\) does not fit into any column block, and the instance is a no-instance. If \(b=a+2\), then, again, by Condition (1), \(j\) can only fit into a column block where \(\{u_{1s},u_{2s}\}=\{a,a+1\}\). There are at most two such column blocks: we write \(s_{j,1}\) and \(s_{j,2}\) for their indices (\(s_{j,1}=s_{j,2}\) if a single column block fits). The other easy case is when \(b=a\), _i.e._, all values in column \(j\) are equal to \(a\). If \(j\) fits into column block \(J_{s}\), then, with Conditions (2) and (3), \(a\in U_{1s}\cap U_{2s}\), and \(J_{s}\) is one of the at most two column blocks having \(\beta=a\): again, we write \(s_{j,1}\) and \(s_{j,2}\) for their indices. Finally, consider a column \(j\) with \(b=a+1\), and let \(s\in[\ell]\) be such that \(j\) fits into \(J_{s}\). Then, by Condition (1), the \"middle-value\" for column block \(J_{s}\) is \(\beta\in\{a,b\}\). The pair \((u_{1s},u_{2s})\) must be from \(\{(a-1,a),(a,a-1),(a,b),(b,a)\}\). We write \(J_{s_{1}},\ldots,J_{s_{4}}\) for the four column blocks (if they exist) corresponding to these four cases. We define \(s_{j,1}=s_{1}\) if \(j\) fits into \(J_{s_{1}}\), and \(s_{j,1}=s_{3}\) otherwise. Similarly, we define \(s_{j,2}=s_{2}\) if \(j\) fits into \(J_{s_{2}}\), and \(s_{j,2}=s_{4}\) otherwise. Consider a solution assigning \(j\) to \(s^{*}\in\{s_{1},s_{3}\}\), with \(s^{*}\
eq s_{j,1}\). Since \(j\) must fit into \(J_{s^{*}}\), the only possibility is that \(s^{*}=s_{3}\) and \(s_{j,1}=s_{1}\). Thus, \(j\) fits into both \(J_{s_{1}}\) and \(J_{s_{3}}\), so Conditions (2) and (3) imply \(\sharp_{j}^{a}\leq h_{1}\) and \(\sharp_{j}^{b}\leq h_{2}\). Since \(\sharp_{j}^{a}+\sharp_{j}^{b}=h_{1}+h_{2}=m\), we have \(\sharp_{j}^{a}=h_{1}\) and \(\sharp_{j}^{b}=h_{2}\). Thus, placing \(j\) in either column block yields the same row partition, namely \(I_{1}=\{i\mid a_{ij}=a\}\) and \(I_{2}=\{i\mid a_{ij}=b\}\). Hence, the solution assigning \(j\) to \(J_{s_{3}}\), can assign it to \(J_{s_{1}}=J_{s_{j,1}}\), instead, without any further need for modification. Similarly, with \(s_{2}\) and \(s_{4}\), any solution assigning \(j\) to \(J_{s_{2}}\) or \(J_{s_{4}}\) can assign it to \(J_{s_{j,2}}\) without any other modification. Thus, since any solution must assign \(j\) to one of \(\{J_{s_{1}},\ldots,J_{s_{4}}\}\), it can assign it to one of \(\{J_{s_{j,1}},J_{s_{j,2}}\}\) instead. We now give the proof of Theorem 7. Proof. : Let \(I=(\mathcal{A}\in\Sigma^{m\times n},k=2,\ell,c=1)\) be a \((2,*)\)-Co-Clustering\({}_{\infty}\) instance. The proof is by induction on \(\ell\). For \(\ell=1\), the problem is solvable in \(O(n(m+\log n))\) time (Theorem 4). We now consider general values of \(\ell\). Note that if \(\ell\) is large compared to \(m\) (that is, \(2^{m}<|\Sigma|^{\ell}\)), then one can directly guess the row partition and run the algorithm of Lemma 2. Thus, for the running time bound, we now assume that \(\ell<m\). By Observation 2, we can assume that \(\Sigma\subset\mathbb{Z}\).