Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth

We give an algorithm that given a graph G with n vertices and m edges and an integer k, in time Oₖ(n¹⁺ᵒ⁽¹⁾) + O(m) either outputs a rank decomposition of G of width at most k or determines that the rankwidth of G is larger than k; the Oₖ(·)-notation hides factors depending on k. Our algorithm returns also a (2ᵏ⁺¹-1)-expression for cliquewidth, yielding a (2ᵏ⁺¹-1)-approximation algorithm for cliquewidth with the same running time. This improves upon the Oₖ(n²) time algorithm of Fomin and Korhonen [STOC 2022]. The main ingredient of our algorithm is a fully dynamic algorithm for maintaining rank decompositions of bounded width: We give a data structure that for a dynamic n-vertex graph G that is updated by edge insertions and deletions maintains a rank decomposition of G of width at most $4k$ under the promise that the rankwidth of G never grows above k. The amortized running time of each update is Oₖ(2√log n log log n). The data structure furthermore can maintain whether G satisfies some fixed CMSO₁ property within the same running time. We also give a framework for performing ``dense'' edge updates inside a given set of vertices X, where the new edges inside X are described by a given CMSO₁ sentence and vertex labels, in amortized Oₖ(|X| · 2√log n log log n) time. Our dynamic algorithm generalizes the dynamic treewidth algorithm of Korhonen, Majewski, Nadara, Pilipczuk, and Soko{}owski [FOCS 2023].