## 1 Introduction
Furthermore, we provide the new result that Pattern-Guided \(2\)-Anonymity is polynomial-time solvable (Theorem 2). Formal Introduction of the New Model.A _row type_ is a maximal set of identical rows of a matrix. **Definition 1**. : _(\(k\)-anonymous [15, 16, 17]) A matrix is \(k\)-anonymous if every row type contains at least \(k\) rows in the matrix, that is, for every row in the matrix, one can find at least \(k-1\) other identical rows._  
Matrices are made \(k\)-anonymous by suppressing some of their entries. Formally, _suppressing_ an entry \(M[i,j]\) of an \(n\times m\)-matrix \(M\) over alphabet \(\Sigma\) with \(1\leq i\leq n\) and \(1\leq j\leq m\) means to simply replace \(M[i,j]\in\Sigma\) by the new symbol \"\(\star\)\", ending up with a matrix over the alphabet \(\Sigma\cup\{\star\}\). Our central enhancement of the \(k\)-Anonymity model lies in the user-specific pattern mask guiding the anonymization process: Every row in the \(k\)-anonymous output matrix has to conform to one of the given pattern vectors. Note that both the input table and the given patterns mathematically are matrices, but we use different terms to more easily distinguish between them: the \"pattern mask\" consists of \"pattern vectors\", and the \"input matrix\" consists of \"rows\". **Definition 2**. : _A row \(r\) in a matrix \(M\in\{\Sigma,\star\}^{n\times m}\) matches a pattern vector \(v\in\{\square,\star\}^{m}\) if and only if \(\forall 1\leq i\leq m:r[i]=\star\iff v[i]=\star,\) that is, \(r\) and \(v\) have \(\star\)-symbols at the same positions._  
With these definitions, we can now formally define our central computational problem. The decisive difference with respect to our previous model [13] is that in our new model, two non-identical output rows can match the same pattern vector. Pattern-Guided \(k\)-Anonymity  
**Input:** A matrix \(M\in\Sigma^{n\times m}\), a pattern mask \(P\in\{\square,\star\}^{p\times m}\), and two positive integers \(k\) and \(s\). **Question:** Can one suppress at most \(s\) entries of \(M\) in order to obtain a \(k\)-anonymous matrix \(M^{\prime}\), such that each row type of \(M^{\prime}\) matches to at least one pattern vector of \(P\)? For some concrete examples, we refer to Section 3.6. Our ResultsDescribing a polynomial-time many-to-one reduction from the NP-hard 3-Set Cover problem, we show that Pattern-Guided \(k\)-Anonymity is NP-complete; even if the input matrix only consists of three columns, there are only two pattern vectors, and \(k=3\). Motivated by this computational intractability result, we develop an exact algorithm that solves Pattern-Guided \(k\)-Anonymity in \(O(2^{tp}t^{\xi}p^{5}m+nm)\) time for an \(n\times m\) input matrix \(M\), \(p\) pattern vectors, and the number of different rows in \(M\) being \(t\). In other words, this shows that Pattern-Guided \(k\)-Anonymity is fixed-parameter tractable for the combined parameter \((t,p)\) and actually can be solved in linear time if \(t\) and \(p\) take constant values. (The fundamental idea behind parameterized complexity analysis [18, 19, 20] is, given a computationally hard problem \(Q\) to identify a parameter \(\ell\) (typically, a positive integer or a tuple of positive integers), for \(Q\) and to determine whether size-\(s\) instances of \(Q\) can be solved in \(f(\ell)\cdot s^{O(1)}\) time, where \(f\) is an arbitrary computable function.) This result appears to be of practical interest only in special cases (\"small\" values for \(t\) and \(p\) are needed). It nevertheless paves the way for a formulation of an integer linear program for Pattern-Guided \(k\)-Anonymity that exactly solves moderate-size instances of Pattern-Guided \(k\)-Anonymity in reasonable time. Furthermore, our fixed-parameter tractability result also leads to a simple and efficient greedy heuristic, whose practical competitiveness is underlined by a set of experiments with real-world data, also favorably comparing with the Mondrian algorithm for \(k\)-Anonymity[21].