Édouard Bonnet

activity

20232026

collaborators

17 papers

cs.DS2026

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators

Édouard Bonnet, Yeonsu Chang

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 ⩽ b < 1$ , every graph in the class with $m$ edges admits a balanced separator of si…

cs.CC2026

Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor

Édouard Bonnet, Yeonsu Chang

We show that there is a fixed planar graph $H$ , namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$ -induced-minor-free graphs. This refutes the Dalla…

cs.DS2026

Faster Parameterized Broadcasting

Édouard Bonnet, Carl Feghali, Manolis Vasilakis

Given a connected graph $G$ and a source $s \in V (G)$ , what is the smallest number of rounds necessary for all vertices of $G$ to receive a message initially only held by $s$ , wher…

cs.CC2026

Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

Édouard Bonnet, Maël Dumas, Julien Duron

For every $ε > 0$ , Max Independent Set admits a polynomial-time $n^{ε}$ -approximation algorithm on $n$ -vertex graphs of effectively bounded twin-width [Bergé et a…

cs.DS2026

Moderately beyond clique-width: reduced component max-leaf and related parameters

Édouard Bonnet, Yeonsu Chang, Julien Duron +2

Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…

math.CO2026

Coarse Balanced Separators in Fat-Minor-Free Graphs

Édouard Bonnet, Hung Le, Marcin Pilipczuk +1

Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…

cs.CC2025

Coloring Hardness on Low Twin-Width Graphs

Édouard Bonnet

As the class $T_{4}$ of graphs of twin-width at most 4 contains every finite subgraph of the infinite grid and every graph obtained by subdividing each edge of an $n$ -vertex…

math.CO2025

Excluding a Forest Induced Minor

Édouard Bonnet, Benjamin Duhamel, Robert Hickingbotham

In the first paper of the Graph Minors series [JCTB '83], Robertson and Seymour proved the Forest Minor theorem: the $H$ -minor-free graphs have bounded pathwidth if and only if $H$ …

cs.DS2025

Separator Theorem for Minor-Free Graphs in Linear Time

Édouard Bonnet, Tuukka Korhonen, Hung Le +2

The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with $n$ vertices has a balanced separator of siz…

math.CO2025

Every Graph is Essential to Large Treewidth

Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana +1

We show that for every graph $H$ , there is a hereditary weakly sparse graph class $C_{H}$ of unbounded treewidth such that the $H$ -free (i.e., excluding $H$ as an induced su…

cs.CC2025

Induced Disjoint Paths Without an Induced Minor

Pierre Aboulker, Édouard Bonnet, Timothé Picavet +1

We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs -- which avoids the 1-subdivis…

cs.CC2025

Mim-Width is paraNP-complete

Benjamin Bergougnoux, Édouard Bonnet, Julien Duron

We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Widt…

math.CO2024

Adjacency Labeling Schemes for Small Classes

Édouard Bonnet, Julien Duron, John Sylvester +1

A graph class admits an implicit representation if, for every positive integer $n$ , its $n$ -vertex graphs have a $O (lo g n)$ -bit (adjacency) labeling scheme, i.e., their vertices c…

math.CO2024

Sparse Induced Subgraphs of Large Treewidth

Édouard Bonnet

Motivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Sey…

cs.DS2024

Symmetric-Difference (Degeneracy) and Signed Tree Models

Édouard Bonnet, Julien Duron, John Sylvester +1

We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…

math.CO2024

Graphs without a 3-connected subgraph are 4-colorable

Édouard Bonnet, Carl Feghali, Tung Nguyen +4

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…

math.CO2023

Tight bounds on adjacency labels for monotone graph classes

Édouard Bonnet, Julien Duron, John Sylvester +2

A class of graphs admits an adjacency labeling scheme of size $b (n)$ , if the vertices in each of its $n$ -vertex graphs can be assigned binary strings (called labels) of length $b(n…