## 2 Complexity and Algorithms
### Parameterized Complexity
#### Simplex Matching
By construction, \(P(M(e))\
eq\emptyset\). We construct \(M^{\prime}\) from \(M\) by suppressing for each \(e\in E^{\prime}\) entries in the rows \(M(e)\) such that they match \(p(e)\). Observe that \(M^{\prime}\) is \(k\)-anonymous, and each row matches a pattern vector. Furthermore, by construction, there are at most \(s\) suppressions in \(M^{\prime}\). Thus, \((M,P,2,s)\) is a yes-instance. Contrasting the general intractability result of Theorem 1, we will show fixed-parameter tractability with respect to the combined parameter \((|\Sigma|,m)\). To this end, we additionally use as a parameter the number \(t\) of different input rows. Indeed, we show fixed-parameter tractability with respect to the combined parameter \((t,p)\). This implies fixed-parameter tractability with respect to the combined parameter \((|\Sigma|,m)\), as \(|\Sigma|^{m}\geq t\) and \(|\Sigma|^{m}\geq 2^{m}\geq p\). This results from an adaption of combinatorial algorithms from previous work [13, 27]. Before presenting the algorithm, we introduce some notation. We distinguish between the _input_ row types of the input matrix \(M\) and the _output_ row types of the matrix \(M^{\prime}\). Note that in the beginning, we can compute the input row types of \(M\) in \(O(nm)\) time using a trie [28], but the output row types are unknown. By the definition of Pattern-Guided \(k\)-Anonymity, each output row type \(R^{\prime}\) has to match a pattern vector \(v\in P\). We call \(R^{\prime}\) an _instance_ of \(v\). **Theorem 3**. : Pattern-Guided \(k\)-Anonymity _can be solved in \(O(2^{tp}\cdot t^{6}p^{5}\cdot m+nm)\) time, where \(p\) is the number of pattern vectors and \(t\) is the number of different rows in the input matrix \(M\)._  
Proof. : We present an algorithm running in two phases:  
**Phase 1:**: Guess for each possible output row type whether it is used in \(M^{\prime}\). Denote with \(\mathcal{R}\) the set of all output row types in \(M^{\prime}\) according to the guessing result. **Phase 2:**: Check whether there exists a \(k\)-anonymous matrix \(M^{\prime}\) that can be obtained from \(M\) by suppressing at most \(s\) elements, such that \(M^{\prime}\) respects the guessing result in Phase 1; that is, the set of row types in \(M^{\prime}\) is exactly \(\mathcal{R}\). Row Assignment  
**Input:** Nonnegative integers \(k\), \(s\), \(\omega_{1},\ldots,\omega_{r}\) and \(n_{1},\ldots,n_{t}\) with \(\sum_{i=1}^{t}n_{i}=n\), and a function \(h:\)  
\(T_{\text{in}}\times T_{\text{out}}\to\{0,1\}\). **Question:** Is there a function \(g:T_{\text{in}}\times T_{\text{out}}\to\{0,\ldots,n\}\), such that:\[h(i,j)\cdot n\geq g(i,j) \forall i\in T_{\text{in}}\,\forall j\in T_{\text{out}} \tag{1}\] \[\sum_{i=1}^{t}g(i,j)\geq k \forall j\in T_{\text{out}}\] (2) \[\sum_{j=1}^{p}g(i,j)=n_{i} \forall i\in T_{\text{in}}\] (3) \[\sum_{i=1}^{t}\sum_{j=1}^{p}g(i,j)\cdot\omega_{j}\leq s \tag{4}\]  
We now discuss how we use Row Assignment to solve Phase 2. The function \(h\) captures the guessing in Phase 1: If the input row type \(i\) is \"compatible\" with the output row type \(j\), then \(h(i,j)=1\), otherwise, \(h(i,j)=0\). Here, an input row type \(R\) is _compatible_ with an output row type \(R^{\prime}\) if the rows in both row types are identical in the non-\(\star\)-positions or, equivalently, if any row of \(R\) can be made identical to any row of \(R^{\prime}\) by just replacing entries with the \(\star\)-symbol. The integer \(\omega_{i}\) is set to the number of stars in the \(i^{\text{th}}\) output row type \(R_{i}\) in \(\mathcal{R}\); that is, \(\omega_{i}\) captures the cost of \"assigning\" a compatible row of \(M\) to \(R_{i}\). In \(n_{i}\), the size (number of rows) of the \(i^{\text{th}}\) input row type is stored. The integers with the same names in Row Assignment and Pattern-Guided \(k\)-Anonymity also store the same values.