Combinatorics Seminar

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).

w3c valid   accessible website
redesigned by barak soreq