# Co-Clustering under the Maximum Norm+
## 4 Tractability Results
### Fixed-Parameter Tractability  
We develop an algorithm solving \((2,*)\)-Co-Clustering\({}_{\infty}\) for \(c=1\) based on our reduction to CNF-SAT (see Lemma 1). The main idea is, given matrix \(\mathcal{A}\) and cluster boundary \(\mathcal{U}\), to simplify the Boolean formula \(\phi_{\mathcal{A}\mathcal{U}}\) into a 2-Sat formula, which can be solved efficiently. This is made possible by the constraint on the cost, which imposes a very specific structure on the cluster boundary. This approach requires to enumerate all (exponentially many) possible cluster boundaries, but yields fixed-parameter tractability for the combined parameter \((\ell,|\Sigma|)\). Theorem 7: \((2,*)\)-Co-Clustering\({}_{\infty}\) _is \(O(|\Sigma|^{3\ell}n^{2}m^{2})\)-time solvable for \(c=1\)._  
In the following, we prove Theorem 7 in several steps. A first sub-result for the proof of Theorem 7 is the following lemma, which we use to solve the case where the number \(2^{m}\) of possible row partitions is less than \(|\Sigma|^{\ell}\). Lemma 2: _For a fixed row partition \(\mathcal{I}\), one can solve Co-Clustering\({}_{\infty}\) in \(O(|\Sigma|^{k\ell}mn\ell)\) time. Moreover, Co-Clustering\({}_{\infty}\) is fixed-parameter tractable with respect to the combined parameter (\(m,k,\ell,c\))._  
Proof: Given a fixed row partition \(\mathcal{I}\), the algorithm enumerates all \(|\Sigma|^{k\ell}\) different cluster boundaries \(\mathcal{U}=(u_{rs})\). We say that a given column \(j\)_fits_ in column block \(J_{s}\) if, for each \(r\in[k]\) and \(i\in I_{r}\), we have \(a_{ij}\in[u_{rs},u_{rs}+c]\) (this can be decided in \(O(m)\) time for any pair \((j,s)\)). The input is a yes-instance if and only if for some cluster boundary \(\mathcal{U}\), every column fits in at least one column block. Fixed-parameter tractability with respect to \((m,k,\ell,c)\) is obtained from two simple further observations. First, all possible row partitions can be enumerated in \(O(k^{m})\) time. Second, since each of the \(k\ell\) clusters contains at most \(c+1\) different values, the alphabet size \(|\Sigma|\) for yes-instances is upper-bounded by \((c+1)k\ell\). The following lemma, also used for the proof of Theorem 7, yields that even for the most difficult instances, there is no need to consider more than two column clusters to which any column can be assigned. Lemma 3: _Let \(I=(\mathcal{A}\in\Sigma^{m\times n},k=2,\ell,c=1)\) be an instance of \((2,*)\)-Co-Clustering\({}_{\infty}\), \(h_{1}\) be an integer, \(0<h_{1}<m\), and \(\mathcal{U}=(u_{rs})\) be a cluster boundary with pairwise different columns, such that \(|u_{1s}-u_{2s}|=1\) for all \(s\in[\ell]\)._  
_Then, for any column \(j\in[n]\), two indices \(s_{j,1}\) and \(s_{j,2}\) can be computed in time \(O(mn)\), such that if \(I\) has a solution \((\{I_{1},I_{2}\},\{I_{1},\ldots,I_{\ell}\})\) satisfying \(\mathcal{U}\) with \(|I_{1}|=h_{1}\), then it has one where each column \(j\) is assigned to either \(J_{s_{j,1}}\) or \(J_{s_{j,2}}\)._  
Proof: We write \(h_{2}=m-h_{1}\) (\(h_{2}=|I_{2}|>0\) for any solution with \(h_{1}=|I_{1}|\)). Given a column \(j\in[n]\) and any element \(a\in\Sigma\), we write \(\sharp^{a}_{j}\) for the number of entries with value \(a\) in column \(j\). Consider a column block \(J_{s}\subseteq[n]\), \(s\in[\ell]\). Write \(\alpha,\beta,\gamma\) for the three values, such that \(U_{1s}\setminus U_{2s}=\{\alpha\}\), \(U_{1s}\cap U_{2s}=\{\beta\}\) and \(U_{2s}\setminus U_{1s}=\{\gamma\}\). Note that \(\{\alpha,\beta,\gamma\}=\{\beta-1,\beta,\beta+1\}\). We say that column \(j\)_fits_ into column block \(J_{s}\) if the following three conditions hold:  
1. \(\sharp^{x}_{j}=0\) for any \(x\
otin\{\alpha,\beta,\gamma\}\),
2. \(\sharp^{a}_{j}\leq h_{1}\) and
3. \(\sharp^{j}_{j}\leq h_{2}\). Note that if Condition (1) is violated, then the column contains an element that is neither in \(U_{1s}\) nor in \(U_{2s}\).