## 2 Complexity and Algorithms
### Parameterized Complexity
#### Simplex Matching  
**Input:**: A hypergraph \(H=(V,E)\) with hyperedges of size two and three, a positive integer \(h\), and a cost function, \(\mathrm{cost}\colon E\to\mathds{N}\), such that:  
1. \(\{u,v,w\}\in E\Rightarrow\{u,v\},\{v,w\},\{u,w\}\in E\) and
2. \(\mathrm{cost}(\{u,v\})+\mathrm{cost}(\{v,w\})+\mathrm{cost}(\{u,w\})\leq 2 \cdot\mathrm{cost}(\{u,v,w\})\). **Question:**: Is there a subset of the hyperedges \(E^{\prime}\subseteq E\), such that for all \(v\in V\), there is exactly one edge in \(E^{\prime}\) containing \(v\) and \(\sum_{e\in E^{\prime}}\mathrm{cost}(e)\leq h\)? We slightly adjust their reduction to obtain polynomial-time solvability for Pattern-Guided \(2\)-Anonymity, together with Theorem1, yielding a complexity dichotomy for Pattern-Guided \(k\)-Anonymity with respect to the parameter \(k\). **Theorem 2**. : Pattern-Guided \(2\)-Anonymity _is polynomial-time solvable._  
Proof. : We reduce Pattern-Guided \(2\)-Anonymity to Simplex Matching. To this end, we first introduce some notation. Let \((M,P,2,s)\) be the Pattern-Guided \(2\)-Anonymity instance. For a set \(A\) of rows \(A=\{r_{1},\ldots,r_{\ell}\}\) and a pattern vector \(p\) in \(P\) the set \(A(p)\) is obtained from \(A\) by suppressing entries in the rows of \(A\) such that each row matches \(p\) (see Definition2). The set \(P(A)\) contains all pattern vectors \(p\) such that \(A(p)\) is a set of identical rows. Intuitively, \(P(A)\) contains all \"suitable\" pattern vectors to make the rows in \(A\) identical. Now, construct the hypergraph \(H=(V,E)\) as follows: Initialize \(V=\emptyset\) and \(E=\emptyset\). For each row \(r\) in \(M\) add a vertex \(v_{r}\) to \(V\). For a vertex subset \(V^{\prime}\subseteq V\) let \(M(V^{\prime})\) be the set of the corresponding rows in \(M\). For each vertex subset \(V^{\prime}\subseteq V\) of size \(2\leq|V^{\prime}|\leq 3\) add the hyperedge \(V^{\prime}\) if \(P(M(V^{\prime}))\
eq\emptyset\). Let \(p(V^{\prime})\) be a pattern vector in \(P(M(V^{\prime}))\) with the minimum number of \(\star\)-symbols. Denote this number of \(\star\)-symbols of \(p(V^{\prime})\) by \(\ell\). Then, set \(\mathrm{cost}(V^{\prime})=\ell\cdot|V^{\prime}|\). Note that this is exactly the cost to \"anonymize\" the rows in \(M(V^{\prime})\) with the pattern vector \(p\). Finally, set the cost bound \(h=s\). This completes the construction. First, we show that Conditions1 and 2 are fulfilled. Clearly, as each pattern vector that makes some row set \(A\) identical also makes each subset of \(A\) identical, it follows that for any \(V^{\prime}\subseteq V\) and any \(V^{\prime\prime}\subseteq V\), it holds \(P(M(V^{\prime}))\subseteq P(M(V^{\prime\prime}))\). Hence, Condition1 is fulfilled. Furthermore, it follows that \(2\cdot\mathrm{cost}(\{u,v,w\})\geq 3\cdot\mathrm{cost}(\{u,v\})\) for each \(u,v,w\in V\), implying:  
\[\mathrm{cost}(\{u,v\})+\mathrm{cost}(\{v,w\})+\mathrm{cost}(\{u,w\})\leq\sfrac {6}{3}\cdot\mathrm{cost}(\{u,v,w\})\]  
Thus, Condition2 is fulfilled. Observe that the construction can be easily performed in polynomial time. Hence, it remains to be shown that \((M,P,2,s)\) is a yes-instance of Pattern-Guided \(2\)-Anonymity, if and only if \((H,s,\mathrm{cost})\) is a yes-instance of Simplex Matching. \"\(\Rightarrow\):\" Let \(M^{\prime}\) be a \(2\)-anonymous matrix obtained from \(M\) by suppressing at most \(s\) elements, and each row of \(M^{\prime}\) matches a pattern vector in \(P\). Let \(\mathcal{R}\) be the set of all row types in \(M^{\prime}\). We construct a matching \(E^{\prime}\) for \(H\) as follows: First, partition the rows in each row type, such that each part contains two or three rows. For each part \(Q\), add to \(E^{\prime}\) the set of the vertices corresponding to the rows in \(Q\). By construction, the cost bound is satisfied, and all vertices are matched. \"\(\Leftarrow\):\" Let \(E^{\prime}\subseteq E\) be a matching, and let \(e\in E^{\prime}\). Recall that \(M(e)\) denotes the set of rows corresponding to the vertices in \(e\).