When: Sunday, April 21, 10am
Where: Schreiber 309
Speaker: G. Z. Gutin, Royal Holloway, University of London
Title: Parameterized Complexity of Access Control Problems
The Workflow Satisfiability Problem (WSP) is defined as follows. We are given sets $S=\{s_1,\ldots ,s_k\}$ of steps and $U=\{u_1,\ldots ,u_n\}$ of users. For every step $s_i$ we have a list $L(s_i)$ of users that are allowed to do it. There are relations $\rho_j\subseteq U\times U$ and some constraints of the form $(\rho_j, S', S'')$ where $S',S''\subseteq S$.
We are to decide whether there is a function $\pi:\ S \rightarrow U$ satisfying the following conditions:
* $\pi(s_j)\in L(s_j)$;
* Each constraint $(\rho_j, S', S'')$ must be satisfied, i.e., there are $s'\in S',\ s''\in S''$ such that $(\pi(s'),\pi(s''))\in \rho_j$.
Let k-WSP be WSP with parameter k (k is often small in practice).
Wang and Li (2010) showed that (i) WSP is NP-complete, (ii) k-WSP is W[1]-hard (iii) WSP(=,\neq) is fixed-parameter tractable. Here $=$ and $\neq$ are the relations $\{(s,s): s\in S\}$ and $\{(s,s'): s\neq s'\in S\}$, respectively.
We significantly improve the FPT-algorithms of Wang and Li and prove that our algorithms cannot be significantly improved any further unless the Exponential Time Hypothesis fails, extend the set of relations, and investigate some cases when WSP has polynomial kernel or not (subject to a well-known complexity theory hypothesis). Our results also improve some results of Fellows et al. (2011) on a problem related to WSP(\neq).
Joint work with Jason Crampton (Information Security Group, RHUL) and Anders Yeo (Singapore Univ. Design and Technology).