Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints

by Daniel Karapetyan, Andrei Gagarin, Gregory Gutin

Abstract:

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.

Reference:

Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints (Daniel Karapetyan, Andrei Gagarin, Gregory Gutin), In proc. of 9th International Frontiers of Algorithmics Workshop, 3–5 July 2015, Guilin, Guangxi, China, Lecture Notes in Computer Science 9130, 138–149, Springer, 2015.

Bibtex Entry:

@InProceedings{Karapetyan2015, Title = {Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints}, Author = {Karapetyan, Daniel and Gagarin, Andrei and Gutin, Gregory}, Booktitle = {9th International Frontiers of Algorithmics Workshop, 3--5 July 2015}, Year = {2015}, Address = {Guilin, Guangxi, China}, Pages = {138--149}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {9130}, Abstract = {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.}, Archiveprefix = {arXiv}, Arxivid = {1412.7834}, Comment = {[<a href="http://dx.doi.org/10.6084/m9.figshare.1360237">Source code and instance generator</a>]}, DOI = {10.1007/978-3-319-19647-3_13}, Eprint = {1412.7834} }