1 citations · 1 across the 8 of their papers we have counts for
17 papers
Small Independent Sets versus Small Separator in Geometric Intersection Graphs
Malory Marin, Rémi Watrigant
While most classical NP-hard graph problems cannot be solved in time on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomen…
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
Pierre Bergé, Édouard Bonnet, Hugues Déprés +1
For any , we give a polynomial-time -approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an -sequence.…
1-Extendability of independent sets
Pierre Bergé, Anthony Busson, Carl Feghali +1
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 th…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time for -vertex graphs given with a witness that th…
Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
The twin-width of a graph is the minimum integer such that has a -contraction sequence, that is, a sequence of iterated vertex identifications for which t…
An algorithmic weakening of the Erdős-Hajnal conjecture
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran +1
We study the approximability of the Maximum Independent Set (MIS) problem in -free graphs (that is, graphs which do not admit as an induced subgraph). As one motivation we i…
Twin-width I: tractable FO model checking
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé +1
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes…
When Maximum Stable Set can be solved in FPT time
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé +1
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic -hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restr…
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Édouard Bonnet, Diana-Elena Fălămaş, Rémi Watrigant
Given a hypergraph , the Minimum Connectivity Inference problem asks for a graph on the same vertex set as with the minimum number of edges such that the subgraph induced by…
Parameterized Complexity of Independent Set in H-Free Graphs
Édouard Bonnet, Nicolas Bousquet, Pierre Charbit +2
In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of -free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given…
Complexity Dichotomies for the Minimum F-Overlay Problem
Nathann Cohen, Frédéric Havet, Dorian Mazauric +2
For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of…
The Authorization Policy Existence Problem
Pierre Bergé, Jason Crampton, Gregory Gutin +1
Constraints such as separation-of-duty are widely used to specify requirements that supplement basic authorization policies. However, the existence of constraints (and authorizatio…
Parameterized Resiliency Problems via Integer Linear Programming
Jason Crampton, Gregory Gutin, Martin Koutecký +1
We introduce an extension of decision problems called resiliency problems. In resiliency problems, the goal is to decide whether an instance remains positive after any (appropriate…
A Multivariate Approach for Checking Resiliency in Access Control
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 \s…
The Bi-Objective Workflow Satisfiability Problem and Workflow Resiliency
Jason Crampton, Gregory Gutin, Daniel Karapetyan +1
A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform parti…
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau +1
In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). An input of this problem is defined by disjoint…