15 citations · 87 across the 33 of their papers we have counts for
6 papers · 1 filter
Deciding twin-width at most 4 is NP-complete
Pierre Bergé, Édouard Bonnet, Hugues Déprés
We show that determining if an -vertex graph has twin-width at most 4 is NP-complete, and requires time unless the Exponential-Time Hypothesis fails. Along the…
Twin-width VI: the lens of contraction sequences
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +1
A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Twin-width and polynomial kernels
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald +2
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main re…
Twin-width and permutations
Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez +2
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describi…
4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time
Édouard Bonnet
We show, assuming the Strong Exponential Time Hypothesis, that for every , approximating undirected unweighted Diameter on -vertex -edge graphs with…