Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
This addresses a theoretical gap in constraint-based workflow systems for researchers in computational complexity, but it is incremental as it extends known results to asymmetric constraints.
The paper tackles the workflow satisfiability problem by introducing seniority constraints, which are asymmetric, and proves it is fixed-parameter tractable using new techniques based on tree decompositions, while also establishing a lower bound for hardness.
The workflow satisfiability problem is concerned with determining whether it is possible to find an allocation of authorized users to the steps in a workflow in such a way that all constraints are satisfied. The problem is NP-hard in general, but is known to be fixed-parameter tractable for certain classes of constraints. The known results on fixed-parameter tractability rely on the symmetry (in some sense) of the constraints. In this paper, we provide the first results that establish fixed-parameter tractability of the satisfiability problem when the constraints are asymmetric. In particular, we introduce the notion of seniority constraints, in which the execution of steps is determined, in part, by the relative seniority of the users that perform them. Our results require new techniques, which make use of tree decompositions of the graph of the binary relation defining the constraint. Finally, we establish a lower bound for the hardness of the workflow satisfiability problem.