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 Ok(n1+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 Ok(·)-notation hides factors depending on k. Our algorithm returns also a (2k+1−1)-expression for cliquewidth, yielding a (2k+1−1)-approximation algorithm for cliquewidth with the same running time. This improves upon the Ok(n2) time algorithm of Fomin and Korhonen [STOC 2022].