Édouard Bonnet

activity

20132026

most citedThe Graph Motif problem parameterized by the structure of the input graph

15 citations · 87 across the 33 of their papers we have counts for

collaborators

62 papers

cs.CC2026

Arc Kayles is PSPACE-complete

Édouard Bonnet

We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.

math.CO2026

Large Finite Point Sets Have 4 Collinear Points or a 6-Clique

Édouard Bonnet

We prove that every finite point set of size at least $1 0^{11055931}$ has four collinear points or six points that pairwise see each other. This resolves the first open case of the…

cs.CC2026

Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Édouard Bonnet

For every $ε > 0$ , it is NP-hard to $n^{1 - ε}$ -approximate Max Independent Set in $n$ -vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simpl…

math.CO2023

Factoring Pattern-Free Permutations into Separable ones

Édouard Bonnet, Romain Bourneuf, Colin Geniet +1

We show that for any permutation $π$ there exists an integer $k_{π}$ such that every permutation avoiding $π$ as a pattern is a product of at most $k_{π}$ separable permutations. In ot…

math.CO2023★ 1 cited

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +2

We show that for any natural number $s$ , there is a constant $γ$ and a subgraph-closed class having, for any natural $n$ , at most $γ^{n}$ graphs on $n$ vertices up to isomorphism, bu…

cs.DM2023

Stretch-width

Édouard Bonnet, Julien Duron

We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polyn…

cs.CC2023★ 1 cited

Cutting Barnette graphs perfectly is hard

Édouard Bonnet, Dibyayan Chakraborty, Julien Duron

A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorith…

cs.DS2023

Maximum Independent Set when excluding an induced minor: $K_{1} + t K_{2}$ and $t C_{3} ⊎ C_{4}$

Édouard Bonnet, Julien Duron, Colin Geniet +2

Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time, a…

math.CO2023★ 7 cited

Neighbourhood complexity of graphs of bounded twin-width

Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä +1

We give essentially tight bounds for, $ν (d, k)$ , the maximum number of distinct neighbourhoods on a set $X$ of $k$ vertices in a graph with twin-width at most~ $d$ . Using the celebra…

cs.DS2022

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

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +1

We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity…

cs.DS2022

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

Pierre Bergé, Édouard Bonnet, Hugues Déprés +1

For any $ε > 0$ , we give a polynomial-time $n^{ε}$ -approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O (1)$ -sequence.…

math.CO2022★ 8 cited

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5

A graph is $O_{k}$ -free if it does not contain $k$ pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…

math.CO2022★ 1 cited

Twin-width can be exponential in treewidth

Édouard Bonnet, Hugues Déprés

For any small positive real $ε$ and integer $t > \frac{1}{ε}$ , we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2…

math.GR2022

Twin-width VII: groups

Édouard Bonnet, Colin Geniet, Romain Tessera +1

Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-widt…

cs.DS2022★ 5 cited

Twin-width VIII: delineation and win-wins

Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim +3

We introduce the notion of delineation. A graph class $C$ is said delineated if for every hereditary closure $D$ of a subclass of $C$ , it holds that $\ma…

math.CO2022★ 12 cited

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

Édouard Bonnet, O-joung Kwon, David R. Wood

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$ , each edge incident to exactly o…

cs.CC2021

Deciding twin-width at most 4 is NP-complete

Pierre Bergé, Édouard Bonnet, Hugues Déprés

We show that determining if an $n$ -vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{Ω (n / l o g n)}$ unless the Exponential-Time Hypothesis fails. Along the…

cs.DS2021

Twin-width VI: the lens of contraction sequences

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +1

A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on…

cs.DS2021★ 13 cited

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

Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…

cs.DS2021

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…

cs.LO2021★ 3 cited

Twin-width and permutations

Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez +2

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describi…

cs.DS2021

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

Édouard Bonnet

We show, assuming the Strong Exponential Time Hypothesis, that for every $ε > 0$ , approximating undirected unweighted Diameter on $n$ -vertex $n^{1 + o (1)}$ -edge graphs with…

cs.DS2020

The Complexity of Mixed-Connectivity

Édouard Bonnet, Sergio Cabello

We investigate the parameterized complexity in $a$ and $b$ of determining whether a graph~ $G$ has a subset of $a$ vertices and $b$ edges whose removal disconnects $G$ , or disconnec…

cs.DS2020

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 $ε > 0$ , approximating directed Diameter on $m$ -arc graphs within ratio $7/4 - ε$ requi…

Arc Kayles is PSPACE-complete

Large Finite Point Sets Have 4 Collinear Points or a 6-Clique

Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Factoring Pattern-Free Permutations into Separable ones

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

Stretch-width

Cutting Barnette graphs perfectly is hard

Maximum Independent Set when excluding an induced minor: K1​+tK2​ and tC3​⊎C4​

Neighbourhood complexity of graphs of bounded twin-width

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

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

Twin-width can be exponential in treewidth

Twin-width VII: groups

Twin-width VIII: delineation and win-wins

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

Deciding twin-width at most 4 is NP-complete

Twin-width VI: the lens of contraction sequences

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

Twin-width and polynomial kernels

Twin-width and permutations

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

The Complexity of Mixed-Connectivity

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

Maximum Independent Set when excluding an induced minor: $K_{1} + t K_{2}$ and $t C_{3} ⊎ C_{4}$

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