Édouard Bonnet

collaborators

5 papers

cs.DS2026

Answering Related Questions

Ãdouard Bonnet

We introduce the meta-problem Sidestep $(I^, dist, d)$ for a problem $I^$ , a metric $dist$ over its inputs, and a map $d: \mathbb N \to \mathbb R_+ \cup \{\infty\}…

cs.DS2026

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes

Ãdouard Bonnet, Jadwiga CzyÅ¼ewska, TomÃ¡Å¡ MasaÅÃk +2

We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{MWIS}) in graphs with a bounded number of pairwise vertex-disjoint and non-a…

cs.DS2026

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications

Ãdouard Bonnet, Colin Geniet, Eun Jung Kim +1

A signed tree model of a graph $G$ is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of $G$ , together with 2-colo…

math.CO2025

Separability Properties of Monadically Dependent Graph Classes

Ãdouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5

A graph class $C$ is monadically dependent if one cannot interpret all graphs in colored graphs from $C$ using a fixed first-order interpretation. We prove that m…

math.CO2025

Induced Minors and Region Intersection Graphs

Ãdouard Bonnet, Robert Hickingbotham

We show that for any positive integers $g$ and $t$ , there is a $K_{6}^{(1)}$ -induced-minor-free graph of girth at least $g$ that is not a region intersection graph over the class o…