3 papers
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 , its -vertex graphs have a -bit (adjacency) labeling scheme, i.e., their vertices c…