15 citations · 87 across the 33 of their papers we have counts for
8 papers · 1 filter
The Complexity of Mixed-Connectivity
Édouard Bonnet, Sergio Cabello
We investigate the parameterized complexity in and of determining whether a graph~ has a subset of vertices and edges whose removal disconnects , or disconnec…
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
Édouard Bonnet
We show, assuming the Strong Exponential Time Hypothesis, that for every , approximating directed Diameter on -arc graphs within ratio requi…
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…
Maximum Clique in Disk-Like Intersection Graphs
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Cl…
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim +1
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order , the smallest available color. The problem Grundy Coloring asks how many colors…