April 22, Monday
14:00 – 15:00
{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)$ users that are allowed to do it. There are relations $rho_jsubseteq Utimes 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 relations ${(s,s): sin S}$ and ${(s,s'): sneq s'in S}$, respectively.We 'significantly' improved the FPT-algorithms of Wang and Li and proved that our algorithms cannot be 'significantly' improved any further unless the Exponential Time Hypothesis fails, extended the set of relations, and investigated 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 & Technology) accepted for publication at ACM Transactions on Information and System Security; preliminary version in ACM Conference on Computer and Communications Security 2012, 857-868.