Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem

The workflow satisfiability problem (wsp) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan–an assignment of tasks to authorized users–such that all constraints are satisfied. The wsp is, in fact, the conservative constraint satisfaction problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, $‐{NP}$ ‐complete. It was observed by Wang and Li (ACM Trans Inf Syst Secur 13(4):40, 2010) that the number $k$ of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of wsp regarding parameter $k$ . We take a more detailed look at the kernelization complexity of wsp( $\mathit{\Gamma }$ ) when $\mathit{\Gamma }$ denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in $\mathit{\Gamma }$ are regular: (1) We are able to reduce the number $n$ of users to $n^{\prime }\le k$ . This entails a kernelization to size poly $(k)$ for finite $\mathit{\Gamma }$ , and, under mild technical conditions, to size poly $(k+m)$ for infinite $\mathit{\Gamma }$ , where $m$ denotes the number of constraints. (2) Already wsp( $R$ ) for some $R\in \mathit{\Gamma }$ allows no polynomial kernelization in $k+m$ unless the polynomial hierarchy collapses.