# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Fixed-Parameter Tractability
Given a \((2,\ell)\)-co-clustering \((\mathcal{I}=\{\{1\},\{2\}\},\mathcal{J})\), a cluster boundary \(\mathcal{U}=(u_{rs})\) satisfied by \((\mathcal{I},\mathcal{J})\), and \(U_{rs}=[u_{rs},u_{rs}+c]\), each column block \(J_{s}\in\mathcal{J}\) is said to be:  
* with _equal_ bounds if \(U_{1s}=U_{2s}\),
* with _non-overlapping_ bounds if \(U_{1s}\cap U_{2s}=\emptyset\),
* with _properly overlapping_ bounds otherwise. We first show that instances implying a solution containing at least one column block with equal or non-overlapping bounds can easily be dealt with. Claim 1: If the solution contains a column-block with equal bounds, then it can be computed in \(O(|\Sigma|^{2\ell}n^{2}m^{2})\) time. Proof. : Assume, without loss of generality, that the last column block, \(J_{\ell}\), has equal bounds. We try all possible values of \(u=u_{1\ell}\). Note that column block \(J_{\ell}\) imposes no restrictions on the row partition. Hence, it can be determined independently of the rest of the co-clustering. More precisely, any column with all values in \(U_{1\ell}=U_{2\ell}=[u,u+c]\) can be put into this block, and all other columns have to end up in the \(\ell-1\) other blocks, thus forming an instance of \((2,\ell-1)\)-Co-Clustering\({}_{\text{\tiny{oo}}}\). By induction, each of these cases can be tested in \(O(|\Sigma|^{2(\ell-1)}n^{2}m(\ell-1))\) time. Since we test all values of \(u\), this procedure finds a solution with a column block having equal bounds in \(O(|\Sigma|\cdot|\Sigma|^{2(\ell-1)}n^{2}m(\ell-1))=O(|\Sigma|^{2\ell}n^{2}m^{2})\) time. Claim: If the solution contains a (non-empty) column-block with non-overlapping bounds, then it can be computed in \(O(|\Sigma|^{2\ell}n^{2}m^{2})\) time. Proof. : Write \(s\) for the index of the column block \(J_{s}\) with non-overlapping bounds, and assume that, without loss of generality, \(u_{1s}+c<u_{2s}\). We try all possible values of \(u=u_{2s}\), and we examine each column \(j\in[n]\). We remark that the row partition is entirely determined by column \(j\) if it belongs to column block \(J_{s}\). That is, if \(j\in J_{s}\), then \(I_{1}=\{i\mid a_{ij}<u\}\) and \(I_{2}=\{i\mid a_{ij}\geq u\}\). Using the algorithm described in Lemma 2, we deduce the column partition in \(O(|\Sigma|^{2\ell-1}nm\ell)\) time, which is bounded by \(O(|\Sigma|^{2\ell}n^{2}m^{2})\). We can now safely assume that the solution contains only column blocks with properly overlapping bounds. In a first step, we guess the values of the cluster boundary \(\mathcal{U}=(u_{rs})\). Note that, for each \(s\in[\ell]\), we only need to consider the cases where \(0<|u_{1s}-u_{2s}|\leq c\), that is, for \(c=1\), we have \(u_{2s}=u_{1s}\pm 1\). Note also that, for any two distinct column blocks \(J_{s}\) and \(J_{s^{\prime}}\), we have \(u_{1s}\
eq u_{1,s^{\prime}}\) or \(u_{2s}\
eq u_{2,s^{\prime}}\). We then enumerate all possible values of \(h_{1}=|I_{1}|>0\) (the _height_ of the first row block), and we write \(h_{2}=m-h_{1}=|I_{2}|>0\). Overall, there are at most \((2|\Sigma|)^{\ell}m\) cases to consider. Using Lemma 3, we compute integers \(s_{j,1}\), \(s_{j,2}\) for each column \(j\), such that any solution satisfying the above conditions (cluster boundary \(\mathcal{U}\) and \(|I_{1}|=h_{1}\)) can be assumed to assign each column \(j\) to one of \(J_{s_{j,1}}\) or \(J_{s_{j,2}}\). We now introduce a 2-Sat formula allowing us to simultaneously assign the rows and columns to the possible blocks. Let \(\phi_{\mathcal{A}\mathcal{U}}\) be the formula as provided by Lemma 1. Create a formula \(\phi^{\prime}\) from \(\phi_{\mathcal{A}\mathcal{U}}\) where, for each column \(j\in[n]\), the column clause \(C_{j}\) is replaced by the smaller clause \(C^{\prime}_{j}:=(y_{j,s_{j,1}}\lor y_{j,s_{j,2}})\). Note that \(\phi^{\prime}\) is a 2-Sat formula, since all other clauses \(R_{i}\) or \(B_{ijrs}\) already contain at most two literals. If \(\phi^{\prime}\) is satisfiable, then \(\phi_{\mathcal{A}\mathcal{U}}\) is satisfiable, and \(\mathcal{A}\) admits a \((2,\ell)\)-co-clustering satisfying \(\mathcal{U}\).