# Solving the Workflow Satisfiability Problem using General Purpose Solvers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 7 May 2021.

## Builds on (most cited first, 8 of 8)

- [Iterative Plan Construction for the Workflow Satisfiability Problem](https://mlsanity.com/paper/1306.3649/) (2013)
- [Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints](https://mlsanity.com/paper/1604.05636/) (2016)
- [Pattern Backtracking Algorithm for the Workflow Satisfiability Problem](https://mlsanity.com/paper/1412.7834/) (2014)
- [Valued Workflow Satisfiability Problem](https://mlsanity.com/paper/1501.07814/) (2015)
- [Algorithms for the workflow satisfiability problem engineered for counting constraints](https://mlsanity.com/paper/1504.02420/) (2015)
- [Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis](https://mlsanity.com/paper/1508.06829/) (2015)
- [A Survey on Workflow Satisfiability, Resiliency, and Related Problems](https://mlsanity.com/paper/1706.07205/) (2017)
- [Bounded and Approximate Strong Satisfiability in Workflows](https://mlsanity.com/paper/1904.07234/) (2019)

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

- [Bi-objective Optimization in Role Mining](https://mlsanity.com/paper/2403.16757/) (2024)

## Abstract (arXiv)

The workflow satisfiability problem (WSP) is a well-studied problem in access control seeking allocation of authorised users to every step of the workflow, subject to workflow specification constraints. It was noticed that the number k of steps is typically small compared to the number of users in the real-world instances of WSP; therefore k is considered as the parameter in WSP parametrised complexity research. While WSP in general was shown to be W[1]-hard, WSP restricted to a special case of user-independent (UI) constraints is fixed-parameter tractable (FPT). However, restriction to the UI constraints might be impractical. To efficiently handle non-UI constraints, we introduce the notion of branching factor of a constraint. As long as the branching factors of the constraints are relatively small and the number of non-UI constraints is reasonable, WSP can be solved in FPT time. Extending the results from Karapetyan et al. (2019), we demonstrate that general-purpose solvers are capable of achieving FPT-like performance on WSP with arbitrary constraints when used with appropriate formulations. This enables one to tackle most of practical WSP instances. While important on its own, we hope that this result will also motivate researchers to look for FPT-aware formulations of other FPT problems.