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 k (n 1+o(1) ) + 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 k (•)-notation hides factors depending on k. Our algorithm returns also a (2 k+1 -1)-expression for cliquewidth, yielding a (2 k+1 -1)approximation algorithm for cliquewidth with the same running time. This improves upon the O k (n 2 ) 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 k (2 √ log n log log n ). The data structure furthermore can main-