Julien Duron

activity

20242026

collaborators

Showing cs.CCShow all

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

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…