# Co-Clustering under the Maximum Norm+
## 3 Intractability Results
### Constant Number of Clusters  
We start by showing that for input matrices containing three different entries, Co-Clustering\({}_{\infty}\) is NP-hard even if the co-clustering consists only of nine clusters. **Theorem 1**. : \((3,3)\)_-Co-Clustering\({}_{\infty}\) is NP-hard for \(\Sigma=\{0,1,2\}\)._  
**Proof. ** We prove NP-hardness by reducing from the NP-complete 3-Coloring [15], where the task is to partition the vertex set of a undirected graph into three independent sets. Let \(G=(V,E)\) be a 3-Coloring instance with \(V=\{v_{1},\ldots,v_{n}\}\) and \(E=\{e_{1},\ldots,e_{m}\}\). We construct a \((3,3)\)-Co-Clustering\({}_{\infty}\) instance \((\mathcal{A}\in\{0,1,2\}^{m\times n},k:=3,\ell:=3,c:=1)\) as follows. The columns of \(\mathcal{A}\) correspond to the vertices \(V\), and the rows correspond to the edges \(E\). For an edge \(e_{i}=\{v_{j},v_{j^{\prime}}\}\in\ E\) with \(j<j^{\prime}\), we set \(a_{ij}:=0\) and \(a_{ij^{\prime}}:=2\). All other matrix entries are set to 1. Hence, each row corresponding to an edge \(\{v_{j},v_{j^{\prime}}\}\) consists of 1-entries except for the columns \(j\) and \(j^{\prime}\), which contain 0 and 2 (see Figure 2). Thus, every co-clustering of \(\mathcal{A}\) with a cost at most \(c=1\) puts column \(j\) and column \(j^{\prime}\) into different column blocks. We next prove that there is a \((3,3)\)-co-clustering of \(\mathcal{A}\) with a cost at most \(c=1\) if and only if \(G\) admits a 3-coloring. First, assume that \(V_{1},V_{2},V_{3}\) is a partition of the vertex set \(V\) into three independent sets. We define a \((3,3)\)-co-clustering \((\mathcal{I},\mathcal{J})\) of \(\mathcal{A}\) as follows. The column partition \(\mathcal{J}:=\{I_{1},I_{2},I_{3}\}\) one-to-one corresponds to the three sets \(V_{1},V_{2},V_{3}\), that is \(J_{s}:=\{i\mid v_{i}\in V_{s}\}\) for all \(s\in\{1,2,3\}\). By the construction above, each row has exactly two non-1-entries being 0 and 2. We define the type of a row to be a permutation of \(0,1,2\), denoting which of the column blocks \(J_{1},J_{2},J_{3}\) contain the 0-entry and the 2-entry. For example, a row is of type \((2,0,1)\) if it has a 2 in a column of \(J_{1}\) and a 0 in a column of \(J_{2}\). The row partition \(\mathcal{I}:=\{I_{1},I_{2},I_{3}\}\) is defined as follows: All rows of type \((0,2,1)\) or \((0,1,2)\) are put into \(I_{1}\). Rows of type \((2,0,1)\) or \((1,0,2)\) are contained in \(I_{2}\), and the remaining rows of type \((2,1,0)\) or \((1,2,0)\) are contained in \(I_{3}\). Clearly, for \((\mathcal{I},\mathcal{J})\), it holds that the non-1-entries in any cluster are either all 0 or all 2, implying that \(\text{cost}_{\infty}(\mathcal{I},\mathcal{J})\leq 1\). Next, assume that \((\mathcal{I},\{J_{1},J_{2},J_{3}\})\) is a \((3,3)\)-co-clustering of \(\mathcal{A}\) with a cost at most 1. The vertex sets \(V_{1},V_{2},V_{3}\), where \(V_{s}\) contains the vertices corresponding to the columns in \(J_{s}\), form three independent sets: if an edge connects two vertices in \(V_{s}\), then the corresponding row would have the 0-entry and the 2-entry in the same column block \(J_{s}\), yielding a cost of 2, which is a contradiction. Theorem 1 can even be strengthened further. Corollary 1.: Co-Clustering\({}_{\infty}\) _with \(\Sigma=\{0,1,2\}\) is NP-hard for any \(k\geq 3\), even when \(\ell\geq 3\) is fixed, and the column blocks are forced to have equal sizes \(|J_{1}|=\ldots=|J_{\ell}|\)._  
Figure 2. An illustration of the reduction from 3-Coloring. **Left**: An undirected graph with a proper 3-coloring of the vertices, such that no two neighboring vertices have the same color. **Right**: The corresponding matrix where the columns are labeled by vertices and the rows by edges with a \((3,3)\)-co-clustering of cost one.