Source author record

Rémi Watrigant

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Cryptography and Security Discrete Mathematics math.CO Logic in Computer Science

Catalog footprint

Research overview

7works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

1-Extendability of independent sets

In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in $2^{o(n)}$ time assuming the Exponential Time Hypothesis, where $n$ is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a. Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability.

preprint2021arXiv

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$ -vertex graphs given with a witness that the twin-width is at most $d$ , called $d$ -contraction sequence or $d$ -sequence, and formulas of size $k$ [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$ . In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$ -time algorithms for $k$ -Independent Set, $r$ -Scattered Set, $k$ -Clique, and $k$ -Dominating Set when an $O(1)$ -sequence is provided. We further show how to solve weighted $k$ -Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$ . These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $χ$ -bounded. This significantly extends the $χ$ -boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$ , respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.

preprint2020arXiv

An algorithmic weakening of the Erdős-Hajnal conjecture

We study the approximability of the Maximum Independent Set (MIS) problem in $H$ -free graphs (that is, graphs which do not admit $H$ as an induced subgraph). As one motivation we investigate the following conjecture: for every fixed graph $H$ , there exists a constant $δ> 0$ such that MIS can be $n^{1 - δ}$ -approximated in $H$ -free graphs, where $n$ denotes the number of vertices of the input graph. We first prove that a constructive version of the celebrated Erdős-Hajnal conjecture implies ours. We then prove that the set of graphs $H$ satisfying our conjecture is closed under the so-called graph substitution. This, together with the known polynomial-time algorithms for MIS in $H$ -free graphs (e.g. $P_6$ -free and fork-free graphs), implies that our conjecture holds for many graphs $H$ for which the Erdős-Hajnal conjecture is still open. We then focus on improving the constant $δ$ for some graph classes: we prove that the classical Local Search algorithm provides an $OPT^{1-\frac{1}{t}}$ -approximation in $K_{t,t}$ -free graphs (hence a $\sqrt{OPT}$ -approximation in $C_4$ -free graphs), and, while there is a simple $\sqrt{n}$ -approximation in triangle-free graphs, it cannot be improved to $n^{\frac{1}{4}-\varepsilon}$ for any $\varepsilon > 0$ unless $NP \subseteq BPP$ . More generally, we show that there is a constant $c$ such that MIS in graphs of girth $γ$ cannot be $n^{\frac{c}γ}$ -approximated. Up to a constant factor in the exponent, this matches the ratio of a known approximation algorithm by Monien and Speckenmeyer, and by Murphy. To the best of our knowledge, this is the first strong (i.e., $Ω(n^δ)$ for some $δ> 0$ ) inapproximability result for Maximum Independent Set in a proper hereditary class.

preprint2020arXiv

Twin-width II: small classes

The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$ -contraction sequence, that is, a sequence of $|V(G)|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$ , where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$ . We show that if a graph admits a $d$ -contraction sequence, then it also has a linear-arity tree of $f(d)$ -contractions, for some function $f$ . First this permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$ , for some constant $c$ . This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an $O(\log n)$ -adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that $\log_{Θ(\log \log d)}n$ -subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$ . We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$ -subdivision of $K_n$ has twin-width at least $d$ . Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$ ~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes.

preprint2016arXiv

A Multivariate Approach for Checking Resiliency in Access Control

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.

preprint2016arXiv

The Authorization Policy Existence Problem

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.

preprint2016arXiv

The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Rémi Watrigant

Research overview

Is this your work?

7 publications

1-Extendability of independent sets

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

An algorithmic weakening of the Erdős-Hajnal conjecture

Twin-width II: small classes

A Multivariate Approach for Checking Resiliency in Access Control

The Authorization Policy Existence Problem

The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency

See the researcher in context

Building this map preview