Édouard Bonnet

research

∙ 08/06/2023

Factoring Pattern-Free Permutations into Separable ones

We show that for any permutation π there exists an integer k_π such that...

0 Édouard Bonnet, et al. ∙

research

∙ 07/20/2023

Small But Unwieldy

We show that for any natural number s, there is a constant γ and a subgr...

0 Édouard Bonnet, et al. ∙

research

∙ 05/19/2023

Stretch-width

We introduce a new parameter, called stretch-width, that we show sits st...

0 Édouard Bonnet, et al. ∙

research

∙ 02/22/2023

Cutting Barnette graphs perfectly is hard

A perfect matching cut is a perfect matching that is also a cutset, or e...

0 Édouard Bonnet, et al. ∙

research

∙ 02/16/2023

Maximum Independent Set when excluding an induced minor: K_1 + tK_2 and tC_3 ⊎ C_4

Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excludi...

0 Édouard Bonnet, et al. ∙

research

∙ 01/24/2023

Treewidth is NP-Complete on Cubic Graphs (and related results)

In this paper, we give a very simple proof that Treewidth is NP-complete...

0 Hans L. Bodlaender, et al. ∙

research

∙ 01/10/2023

Neighbourhood complexity of graphs of bounded twin-width

We give essentially tight bounds for, ν(d,k), the maximum number of dist...

0 Édouard Bonnet, et al. ∙

research

∙ 09/24/2022

Twin-width V: linear minors, modular counting, and matrix multiplication

We continue developing the theory around the twin-width of totally order...

0 Édouard Bonnet, et al. ∙

research

∙ 07/15/2022

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

For any ε > 0, we give a polynomial-time n^ε-approximation algorithm for...

0 Pierre Bergé, et al. ∙

research

∙ 06/01/2022

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...

0 Marthe Bonamy, et al. ∙

research

∙ 04/26/2022

Twin-width VII: groups

Twin-width is a recently introduced graph parameter with applications in...

0 Édouard Bonnet, et al. ∙

research

∙ 04/15/2022

Twin-width can be exponential in treewidth

For any small positive real ε and integer t > 1/ε, we build a graph with...

0 Édouard Bonnet, et al. ∙

research

∙ 04/01/2022

Twin-width VIII: delineation and win-wins

We introduce the notion of delineation. A graph class 𝒞 is said delineat...

0 Édouard Bonnet, et al. ∙

research

∙ 02/25/2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

We present a fixed-parameter tractable algorithm for first-order model c...

0 Édouard Bonnet, et al. ∙

research

∙ 02/24/2022

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

In a reduction sequence of a graph, vertices are successively identified...

0 Édouard Bonnet, et al. ∙

research

∙ 12/16/2021

Deciding twin-width at most 4 is NP-complete

We show that determining if an n-vertex graph has twin-width at most 4 i...

0 Pierre Bergé, et al. ∙

research

∙ 10/30/2021

Twin-width VI: the lens of contraction sequences

A contraction sequence of a graph consists of iteratively merging two of...

0 Édouard Bonnet, et al. ∙

research

∙ 10/28/2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Marthe Bonamy, et al. ∙

research

∙ 07/06/2021

Twin-width and polynomial kernels

We study the existence of polynomial kernels, for parameterized problems...

0 Édouard Bonnet, et al. ∙

research

∙ 02/13/2021

Twin-width and permutations

Inspired by a width invariant defined on permutations by Guillemot and M...

0 Édouard Bonnet, et al. ∙

research

∙ 02/05/2021

Twin-width IV: low complexity matrices

We establish a list of characterizations of bounded twin-width for hered...

0 Édouard Bonnet, et al. ∙

research

∙ 01/07/2021

4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3

We show, assuming the Strong Exponential Time Hypothesis, that for every...

0 Édouard Bonnet, et al. ∙

research

∙ 10/09/2020

The Complexity of Mixed-Connectivity

We investigate the parameterized complexity in a and b of determining wh...

0 Édouard Bonnet, et al. ∙

research

∙ 08/26/2020

Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

We show, assuming the Strong Exponential Time Hypothesis, that for every...

0 Édouard Bonnet, et al. ∙

research

∙ 07/28/2020

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

The Cut Count technique and the rank-based approach have lead to sin...

0 Benjamin Bergougnoux, et al. ∙

research

∙ 07/28/2020

Twin-width III: Max Independent Set and Coloring

We recently introduced the graph invariant twin-width, and showed that f...

0 Édouard Bonnet, et al. ∙

research

∙ 06/17/2020

Twin-width II: small classes

The twin-width of a graph G is the minimum integer d such that G has a d...

0 Édouard Bonnet, et al. ∙

research

∙ 04/30/2020

Twin-width I: tractable FO model checking

Inspired by a width invariant defined on permutations by Guillemot and M...

0 Édouard Bonnet, et al. ∙

research

∙ 04/25/2020

An algorithmic weakening of the Erdős-Hajnal conjecture

We study the approximability of the Maximum Independent Set (MIS) proble...

0 Édouard Bonnet, et al. ∙

research

∙ 03/05/2020

Maximum Clique in Disk-Like Intersection Graphs

We study the complexity of Maximum Clique in intersection graphs of conv...

0 Édouard Bonnet, et al. ∙

research

∙ 01/11/2020

Grundy Coloring friends, Half-Graphs, Bicliques

The first-fit coloring is a heuristic that assigns to each vertex, arriv...

0 Pierre Aboulker, et al. ∙

research

∙ 10/04/2019

Maximum Matchings in Geometric Intersection Graphs

Let G be an intersection graph of n geometric objects in the plane. We s...

0 Édouard Bonnet, et al. ∙

research

∙ 09/18/2019

When Maximum Stable Set can be solved in FPT time

Maximum Independent Set (MIS for short) is in general graphs the paradig...

0 Édouard Bonnet, et al. ∙

research

∙ 09/04/2019

Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distanc...

0 Arnab Bhattacharyya, et al. ∙

research

∙ 08/26/2019

Constraint Generation Algorithm for the Minimum Connectivity Inference Problem

Given a hypergraph H, the Minimum Connectivity Inference problem asks fo...

0 Édouard Bonnet, et al. ∙

research

∙ 08/25/2019

Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

Local search is a widely-employed strategy for finding good solutions to...

0 Édouard Bonnet, et al. ∙

research

∙ 07/18/2019

Metric Dimension Parameterized by Treewidth

A resolving set S of a graph G is a subset of its vertices such that no ...

0 Édouard Bonnet, et al. ∙

research

∙ 11/30/2018

The inverse Voronoi problem in graphs

We introduce the inverse Voronoi diagram problem in graphs: given a grap...

0 Édouard Bonnet, et al. ∙

research

∙ 10/10/2018

Parameterized Complexity of Independent Set in H-Free Graphs

In this paper, we investigate the complexity of Maximum Independent Set ...

0 Édouard Bonnet, et al. ∙

research

∙ 03/05/2018

EPTAS for Max Clique on Disks and Unit Balls

We propose a polynomial-time algorithm which takes as input a finite set...

0 Marthe Bonamy, et al. ∙

research

∙ 12/24/2017

Optimality Program in Segment and String Graphs

Planar graphs are known to allow subexponential algorithms running in ti...

0 Édouard Bonnet, et al. ∙

research

∙ 12/13/2017

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Édouard Bonnet, et al. ∙

research

∙ 10/31/2017

Designing RNA Secondary Structures is Hard

An RNA sequence is a word over an alphabet on four elements {A,C,G,U} ca...

0 Édouard Bonnet, et al. ∙

research

∙ 10/02/2017

On the Parameterized Complexity of Red-Blue Points Separation

We study the following geometric separation problem: Given a set R of ...

0 Édouard Bonnet, et al. ∙

research

∙ 10/01/2017

Orthogonal Terrain Guarding is NP-complete

A terrain is an x-monotone polygonal curve, i.e., successive vertices ha...

0 Édouard Bonnet, et al. ∙

Édouard Bonnet

Featured Co-authors