# 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

## Abstract:

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

redesigned by barak soreq