6 papers · 1 filter
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 , every graph in the class with edges admits a balanced separator of si…
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 , namely the grid, such that Max Independent Set remains NP-hard in -induced-minor-free graphs. This refutes the Dalla…
Faster Parameterized Broadcasting
Édouard Bonnet, Carl Feghali, Manolis Vasilakis
Given a connected graph and a source , what is the smallest number of rounds necessary for all vertices of to receive a message initially only held by , wher…
Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width
Édouard Bonnet, Maël Dumas, Julien Duron
For every , Max Independent Set admits a polynomial-time -approximation algorithm on -vertex graphs of effectively bounded twin-width [Bergé et a…
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…
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…