# Pattern Backtracking Algorithm for the Workflow Satisfiability Problem

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Dec 2014.

## 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 authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. (Such an assignment is called valid.) The problem is NP-hard even when restricted to the large class of user-independent constraints. Since the number of steps k is relatively small in practice, it is natural to consider a parametrisation of the WSP by k. We propose a new fixed-parameter algorithm to solve the WSP with user-independent constraints. The assignments in our method are partitioned into equivalence classes such that the number of classes is exponential in k only. We show that one can decide, in polynomial time, whether there is a valid assignment in an equivalence class. By exploiting this property, our algorithm reduces the search space to the space of equivalence classes, which it browses within a backtracking framework, hence emerging as an efficient yet relatively simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art methods and show that it clearly wins the competition on the whole range of our test problems and significantly extends the domain of practically solvable instances of the WSP.