Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis
This provides theoretical limits for algorithm design in workflow authorization systems, particularly for security and access control applications, and is incremental as it builds on prior FPT results.
The paper tackles the Workflow Satisfiability Problem (WSP) by proving tight lower bounds on the running time of fixed-parameter tractable algorithms for two restrictions of the problem, showing that algorithms with running times O*(2^{ck}) and O*(2^{ck log2 k}) for any c<1 are impossible unless the Strong Exponential Time Hypothesis fails.
The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$. Wang and Li (2010) showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) and Cohen et al. (2014) designed FPT algorithms of running time $O^*(2^{k})$ and $O^*(2^{k\log_2 k})$ for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time $O^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$, unless the Strong Exponential Time Hypothesis fails.