3 papers
cs.DS2022
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
math.CO2021
Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +3
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a…
cs.DS2020
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…