## 2 Complexity and Algorithms
### Parameterized Complexity
Furthermore, in each row in \(M^{\prime}\), either the first element is suppressed or the last two elements. Hence, each row of \(M^{\prime}\) matches to one of the two pattern vectors of \(P\). Finally, observe that \(M^{\prime}\) is \(3\)-anonymous: The three rows corresponding to the set \(S_{j}\
otin\mathcal{F}^{\prime}\) are identical: the first column is suppressed, and the next two columns contain the symbol \(S_{j}\). Since \(\mathcal{F}^{\prime}\) is a set cover, there exists for each element \(u_{j}\) a set \(S_{i}\in\mathcal{F}^{\prime}\) such that \(u_{j}\in S_{i}\). Thus, by construction, the two rows corresponding to the element \(u_{j}\), and the row \((u_{j},S_{i},S_{i})\) in \(M\) coincide in \(M^{\prime}\): The first column contains the entry \(u_{j}\) and the other two columns are suppressed. Finally, for each row \((u_{i},S_{j},S_{j})\) in \(M\) that corresponds to a set \(S_{j}\in\mathcal{F}^{\prime}\), the row in \(M^{\prime}\) coincides with the two rows corresponding to the element \(u_{i}\): Again, the first column contains the entry \(u_{i}\) and the other two columns are suppressed. \"\(\Leftarrow\):\" If \((M,P,3,s)\) is a yes-instance of Pattern-Guided \(k\)-Anonymity, then there is a \(3\)-anonymous matrix \(M^{\prime}\), that is obtained from \(M\) by suppressing at most \(s\) elements, and each row of \(M^{\prime}\) matches to one of the two pattern vectors in \(P\). Since \(M\) and, so, \(M^{\prime}\) contain \(2|U|+3|\mathcal{F}|\) rows, \(M^{\prime}\) contains at most \(s=4|U|+3|\mathcal{F}|+3h\) suppressions and each pattern vector contains a \(\star\)-symbol, there are at most \(2|U|+3h\) rows in \(M^{\prime}\) containing two suppressions and at least \(3|\mathcal{F}|-3h\) rows containing one suppression. Furthermore, since the \(2|U|\) rows in \(M\) corresponding to the elements of \(U\) contain the unique symbol \(\triangle\) in the last two columns in \(M^{\prime}\), these rows are suppressed in the last two columns. Thus, at most \(3h\) rows corresponding to sets of \(\mathcal{F}\) have two suppressions in \(M^{\prime}\). Observe that for each set \(S_{i}\in\mathcal{F}\) the entries in the last two columns of the corresponding rows are \(S_{i}\). There is no other occurrence of this entry in \(M\). Hence, the at least \(3|\mathcal{F}|-3h\) rows in \(M^{\prime}\) with one suppression correspond to \(|\mathcal{F}|-h\) sets in \(\mathcal{F}\). Thus, the at most \(3h\) rows in \(M^{\prime}\) that correspond to sets of \(\mathcal{F}\) and contain two suppressions correspond to at most \(h\) sets of \(\mathcal{F}\). Denote these \(h\) sets by \(\mathcal{F}^{\prime}\). We now show that \(\mathcal{F}^{\prime}\) is a set cover for the 3-Set Cover instance. Assume by contradiction that \(\mathcal{F}^{\prime}\) is not a set cover, and hence, there is an element \(u\in U\setminus(\bigcup_{S\in\mathcal{F}^{\prime}}S)\). However, since \(M^{\prime}\) is \(3\)-anonymous, there has to be a row \(r\) in \(M^{\prime}\) that corresponds to some set \(S_{i}\) such that this row coincides with the two rows \(r_{1}^{u}\) and \(r_{2}^{u}\) corresponding to \(u\). Since all rows in \(M^{\prime}\) corresponding to elements of \(U\) contain two suppressions in the last two columns, the row \(r\) also contains two suppressions in the last two columns. Thus, \(S_{i}\in\mathcal{F}^{\prime}\). Furthermore, \(r\) has to coincide with \(r_{1}^{u}\) and \(r_{2}^{u}\) in the first column, that is, \(r\) contains as the entry in the first column the symbol \(u\). Hence, \(u\in S_{i}\), a contradiction. [PERSON] and [PERSON] [7] showed that, while \(3\)-Anonymity is NP-complete [7,8], \(2\)-Anonymity is polynomial-time solvable by reducing it in polynomial time to the polynomial-time solvable, Simplex Matching[26], defined as follows: