Rémi Watrigant

Malory Marin, Rémi Watrigant

While most classical NP-hard graph problems cannot be solved in time $2^{o(n)}$ on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomenon and admit optimal algorithms running in time $2^{O(\sqrt{n})}$ on certain geometric intersection graphs, such as planar graphs or unit disk graphs. In 2018, de Berg et al. developed a general algorithmic framework for such problems on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, achieving running times of the form $2^{O(n^{1-1/d})}$, along with matching lower bounds under ETH. In this paper, we identify problems that do not exhibit the square-root phenomenon, yet still admit subexponential algorithms on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, for every fixed dimension $d \geqslant 2$. We introduce the notion of a weak square-root phenomenon: problems that can be solved in time $2^{\tilde{O}(n^{1-1/(d+1)})}$, and for which matching lower bounds hold under ETH. We develop both an algorithmic framework and a corresponding lower bound framework. As concrete examples, we show that the problems 2-Subcoloring and Two Sets Cut-Uncut exhibit this behavior. Our algorithms rely on a new win-win structural theorem, which can be informally stated as follows: every such graph admits a sublinear separator whose removal leaves connected components with sublinear independence number. To facilitate the design of these algorithms, we introduce a new graph parameter, the $α$-modulator number, which generalizes both the independence number and the vertex cover number.

Pierre Bergé, Jason Crampton, Gregory Gutin et al.

Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorization policies) may mean that a user is unable to fulfill her/his organizational duties because access to resources has been denied. In short, there is a tension between the need to protect resources (using policies and constraints) and the availability of resources. Recent work on workflow satisfiability and resiliency in access control asks whether this tension compromises the ability of an organization to achieve its objectives. In this paper, we develop a new method of specifying constraints which subsumes much related work and allows a wider range of constraints to be specified. The use of such constraints leads naturally to a range of questions related to "policy existence", where a positive answer means that an organization's objectives can be realized. We analyze the complexity of these policy existence questions and, for particular sub-classes of constraints defined by our language, develop fixed-parameter tractable algorithms to solve them.

Jason Crampton, Gregory Gutin, Rémi Watrigant

In recent years, several combinatorial problems were introduced in the area of access control. Typically, such problems deal with an authorization policy, seen as a relation $UR \subseteq U \times R$, where $(u, r) \in UR$ means that user $u$ is authorized to access resource $r$. Li, Tripunitara and Wang (2009) introduced the Resiliency Checking Problem (RCP), in which we are given an authorization policy, a subset of resources $P \subseteq R$, as well as integers $s \ge 0$, $d \ge 1$ and $t \geq 1$. It asks whether upon removal of any set of at most $s$ users, there still exist $d$ pairwise disjoint sets of at most $t$ users such that each set has collectively access to all resources in $P$. This problem possesses several parameters which appear to take small values in practice. We thus analyze the parameterized complexity of RCP with respect to these parameters, by considering all possible combinations of $|P|, s, d, t$. In all but one case, we are able to settle whether the problem is in FPT, XP, W[2]-hard, para-NP-hard or para-coNP-hard. We also consider the restricted case where $s=0$ for which we determine the complexity for all possible combinations of the parameters.

Jason Crampton, Gregory Gutin, Daniel Karapetyan et al.

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a \emph{decision} problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). In this paper, we introduce the \textsc{Bi-Objective Workflow Satisfiability Problem} (\BOWSP), which enables us to solve \emph{optimization} problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, \BOWSP is intractable from both the classical and parameterized complexity point of view. We prove there exists an fixed-parameter tractable (FPT) algorithm to compute a Pareto front for \BOWSP if we restrict our attention to user-independent constraints. We also present a second algorithm to compute a Pareto front which uses mixed integer programming (MIP). We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most of the instances. Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints. We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of \BOWSP.