12 papers
Reducing CMSO to Unbreakable Graphs Cannot be Computable
Colin Geniet, Roohani Sharma
Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula , testing on arbitrary graphs can be reduced to testing it on -unbreakable gr…
Transducing Linear Decompositions of Tournaments
Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
BojaÅczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We…
Moderately beyond clique-width: reduced component max-leaf and related parameters
Ãdouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot
We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed…
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 is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of , together with 2-colo…