## 2 Complexity and Algorithms
### Parameterized Complexity  
One of the decisions made when developing fixed-parameter algorithms is the choice of the parameter. Natural parameters occurring in the problem definition of Pattern-Guided \(k\)-Anonymity are the number \(n\) of rows, the number \(m\) of columns, the alphabet size \(|\Sigma|\), the number \(p\) of pattern vectors, the anonymity degree \(k\), and the cost bound \(s\). In general, the number of rows will arguably be large and, thus, also the cost bound \(s\), tends to be large. Since fixed-parameter algorithms are fast when the parameter is small, trying to exploit these two parameters tends to be of little use in realistic scenarios. However, analyzing the adult dataset [22] prepared as described by [PERSON] _et al._[23], it turns out that some of the other mentioned parameters are small: The dataset has \(m=9\) columns, and the alphabet size is \(73\). Furthermore, it is natural to assume that also the number of pattern vectors is not that large. Indeed, compared to the \(n=32,561\) rows, even the number of _all possible_ pattern vectors \(2^{9}=512\) is relatively small. Finally, there are applications where \(k\), the degree of anonymity, is small [24]. Summarizing, we can state that fixed-parameter tractability with respect to the parameters \(|\Sigma|\), \(m\), \(k\), or \(p\), could be of practical relevance. Unfortunately, by reducing from 3-Set Cover, we can show that Pattern-Guided \(k\)-Anonymity is NP-hard in very restricted cases. **Theorem 1**. : Pattern-Guided \(k\)-Anonymity _is NP-complete even for two pattern vectors, three columns, and \(k=3\)._  
Proof. : We reduce from the NP-hard 3-Set Cover[25]: Given a set family \(\mathcal{F}=\{S_{1},\ldots,S_{\alpha}\}\) with \(|S_{i}|=3\) over a universe \(U=\{u_{1},\ldots,u_{\beta}\}\) and a positive integer \(h\), the task is to decide whether there is a subfamily \(\mathcal{F}^{\prime}\subseteq\mathcal{F}\) of size at most \(h\) such that \(\bigcup_{S\in\mathcal{F}^{\prime}}\!\!S=U\). In the reduction, we need unique entries in the constructed input matrix \(M\). For ease of notation, we introduce the \(\triangle\)-symbol with an unusual semantics. Each occurrence of a \(\triangle\)-symbol stands for a _different_ unique symbol in the alphabet \(\Sigma\). One could informally state this as \"\(\triangle\
eq\triangle\)\". We now describe the construction. Let \((\mathcal{F},U,h)\) be the 3-Set Cover instance. We construct an equivalent instance \((M,P,k,s)\) of Pattern-Guided \(k\)-Anonymity as follows: Initialize \(M\) and \(P\) as empty matrices. Then, for each element \(u_{i}\in U\), add the row \((u_{i},\triangle,\triangle)\) twice to the input matrix \(M\). For each set \(S_{i}\in\mathcal{F}\) with \(S_{i}=\{u_{a},u_{b},u_{c}\}\), add to \(M\) the three rows \((u_{a},S_{i},S_{i})\), \((u_{b},S_{i},S_{i})\), and \((u_{c},S_{i},S_{i})\). Finally, set \(k=3\), \(s=4|U|+3|\mathcal{F}|+3h\), and add to \(P\) the pattern vectors (\(\square\), \(\star\), \(\star\)), and (\(\star\), \(\square\), \(\square\)). We show the correctness of the above construction by proving that \((\mathcal{F},U,h)\) is a yes-instance of 3-Set Cover, if and only if \((M,P,3,s)\) is a yes-instance of Pattern-Guided \(k\)-Anonymity. \"\(\Rightarrow\):\" If \((\mathcal{F},U,h)\) is a yes-instance of 3-Set Cover, then there exists a set cover \(\mathcal{F}^{\prime}\) of size at most \(h\). We suppress the following elements in \(M\): First, suppress all \(\triangle\)-entries in \(M\). This gives \(4|U|\) suppressions. Then, for each \(S_{i}\in\mathcal{F}^{\prime}\), suppress all \(S_{i}\)-entries in \(M\). This gives \(6|\mathcal{F}^{\prime}|\) suppressions. Finally, for each \(S_{j}\
otin\mathcal{F}^{\prime}\), suppress the first column of all rows containing the entry \(S_{j}\). These are \(3(|\mathcal{F}|-|\mathcal{F}^{\prime}|)\) suppressions. Let \(M^{\prime}\) denote the matrix with the suppressed elements. Note that \(M^{\prime}\) contains \(4|U|+3|\mathcal{F}|+3|\mathcal{F}^{\prime}|\leq s\) suppressed entries.