Édouard Bonnet

activity

20232026

collaborators

Showing cs.CCShow all

4 papers · 1 filter

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.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…

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…