Abstract
The fixed parameter tractable (FPT) approach is a powerful tool in tacklingcomputationally hard problems. In this paper, we link FPT results to classicartificial intelligence (AI) techniques to show how they complement each other.Specifically, we consider the workflow satisfiability problem (WSP) which askswhether there exists an assignment of authorised users to the steps in aworkflow specification, subject to certain constraints on the assignment. Itwas shown by Cohen et al. (JAIR 2014) that WSP restricted to the class ofuser-independent constraints (UI), covering many practical cases, admits FPTalgorithms, i.e. can be solved in time exponential only in the number of steps$k$ and polynomial in the number of users $n$. Since usually $k \ll n$ in WSP,such FPT algorithms are of great practical interest as they significantlyextend the size of the problem that can be routinely solved. We give a new view of the FPT nature of the WSP with UI constraints, showingthat it decomposes the problem into two levels. Exploiting this two-levelsplit, we develop a new FPT algorithm that is by many orders of magnitudefaster than the previous state-of-the-art WSP algorithm; and it also has onlypolynomial space complexity whereas the old algorithm takes memory exponentialin $k$, which limits its application. We also provide a new pseudo-boolean (PB) formulation of the WSP with UIconstraints which exploits this new decomposition of the problem into twolevels. Our experiments show that efficiency of solving this new PB formulationof the problem by a general purpose PB solver can be close to the bespoke FPTalgorithm, which raises the potential of using general purpose solvers totackle FPT problems efficiently. We also study the computational performance of various algorithms tocomplement the overly-pessimistic worst-case analysis that is usually done inFPT studies.