Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph classes for which their computation can be achieved in subquadratic time. Using a new recursive scheme based on the structural properties of median graphs, we provide a quasilinear-time algorithm to determine all eccentricities for this well-known family of graphs. The gist of our technique is to identify the balanced and unbalanced parts of the Θ-class decomposition of median graphs, which are then processed using different recursive schemes. The exact running time of our algorithm is in O (n log4 n ). This outcome not only answers a question asked by Bénéteau et al. (2020) but also greatly improves the recent combinatorial algorithm of Berge et al. (2022) for the same problem, running in time O (n1.6408 logO (1) n ).

International audience

We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{Ω(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivided at least $2 \log n$ times have twin-width at most 4. We also show how to encode trigraphs $H$ (2-edge colored graphs involved in the definition of twin-width) into graphs $G$, in the sense that every $d$-sequence (sequence of vertex contractions witnessing that the twin-width is at most $d$) of $G$ inevitably creates $H$ as an induced subtrigraph, whereas there exists a partial $d$-sequence that actually goes from $G$ to $H$. We believe that these facts and their proofs can be of independent interest.

International audience

Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. [2019] designed a linear-time algorithm computing both the Θ-classes and the median set of median graphs. A natural question emerges: is there a linear-time algorithm computing the diameter for median graphs? We answer positively to this question for median graphs G with constant dimension d, i.e. the dimension of the largest induced hypercube of G. We propose a combinatorial algorithm computing the diameter of median graphs with running time O(2O(d log d)n). In particular, since the hypercube Q4 of dimension 4 is not planar, it shows also that the diameter of planar median graphs can be computed in O(n).

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.11.An extended abstract of this paper appeared in the Proceedings of the Seventh ACM Conference on Data and Application Security and Privacy [1]. Research was partially supported by Leverhulme Trust grant RPG-2018-161 and Royal Society Wolfson Research Merit Award.

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 is 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 provide an overview of our results establishing that some policy existence questions, notably for those instances that are restricted to user-independent constraints, are fixed-parameter tractable.

We are interested in Quantum Annealing (QA), an algorithm inspired by quantum theory and Simulated Annealing (SA). It is based on quantum replicas, which explore an energy surface, and are less prone to be trapped in local minima. Moreover, kinetic energy helps replicas to find a global minimum. This method has proved its efficiency for several optimization problems. We start this study by presenting the application of QA to a new problem: the Multidimensional Knapsack Problem (MKP). We then present a new idea to speed up the quantum annealing process by detecting the resemblance between replicas. If many of the replicas exhibit the same properties, our assumption is that these properties will also be present with a high probability in a global solution. Consequently, the QA may restrict certain mutations in order to preserve those similarities. We call this algorithm Restrictive Quantum Annealing (RQA). We establish that RQA has better performances than QA and SA by carrying out an adequate analysis of the RQA performance, taking the Traveling Salesman Problem (TSP) and the above-mentioned MKP as references. We also advance guidelines indicating types of NP-hard problems for which our algorithm is particularly well adapted.