On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem
复制标题
DOI：
10.1145/2487222.2487226
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
J. Crampton;G. Gutin;Anders Yeo
中科院分区：
文献类型：
--
作者：
J. Crampton;G. Gutin;Anders Yeo
工作流规范定义了一组步骤以及必须执行这些步骤的顺序。安全要求可能会对允许哪些用户组执行这些步骤的子集施加约束。一个工作流规范被称为是可满足的，如果存在一个分配的用户的工作流步骤，满足所有的约束。一个算法，用于确定是否存在这样的分配是重要的，无论是作为一个静态分析工具的工作流规范和工作流管理系统的运行时参考监视器的建设。找到这样的分配通常是一个困难的问题，但是Wang和Li [2010]使用参数化复杂性理论的工作表明，在关于工作流规范的合理假设下存在有效的算法。在这篇文章中，我们改进了工作流可满足性问题的复杂性界。我们还概括和扩展的工作流规范中可能定义的约束类型，并证明了可满足性问题仍然是固定参数听话的约束。最后，我们考虑预处理的问题，并证明在一个重要的特殊情况下，在多项式时间内，我们可以减少到一个等价的用户的数量是最多的步骤数的输入。我们还表明，没有这样的减少存在两个自然的扩展，这种情况下，用户的数量由一个多项式的步骤数，提供了一个广泛接受的复杂性理论假设成立。
A workflow specification defines a set of steps and the order in which these steps must be executed. Security requirements may impose constraints on which groups of users are permitted to perform subsets of these steps. A workflow specification is said to be satisfiable if there exists an assignment of users to workflow steps that satisfies all the constraints. An algorithm for determining whether such an assignment exists is important, both as a static analysis tool for workflow specifications and for the construction of runtime reference monitors for workflow management systems. Finding such an assignment is a hard problem in general, but work by Wang and Li [2010] using the theory of parameterized complexity suggests that efficient algorithms exist under reasonable assumptions about workflow specifications. In this article, we improve the complexity bounds for the workflow satisfiability problem. We also generalize and extend the types of constraints that may be defined in a workflow specification and prove that the satisfiability problem remains fixed-parameter tractable for such constraints. Finally, we consider preprocessing for the problem and prove that in an important special case, in polynomial time, we can reduce the given input into an equivalent one where the number of users is at most the number of steps. We also show that no such reduction exists for two natural extensions of this case, which bounds the number of users by a polynomial in the number of steps, provided a widely accepted complexity-theoretical assumption holds.