# Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

arXiv: https://arxiv.org/abs/1508.06829 · HTML: https://mlsanity.com/paper/1508.06829/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2015.

## Built on by (most cited first, 1 of 1)

- [Solving the Workflow Satisfiability Problem using General Purpose Solvers](https://mlsanity.com/paper/2105.03273/) (2021)

## Abstract (arXiv)

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^*(2k) and O^*(2klog2 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^*(2ck) and O^*(2cklog2 k) for the two restrictions of WSP, respectively, with any c<1, unless the Strong Exponential Time Hypothesis fails.