Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth

View PDF

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(\cdot)-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^{\sqrt{\log n} \log \log n}). The data structure furthermore can maintain whether G satisfies some fixed {\sf CMSO}_1 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 {\sf CMSO}_1 sentence and vertex labels, in amortized O_k(|X| \cdot 2^{\sqrt{\log n} \log \log n}) time. Our dynamic algorithm generalizes the dynamic treewidth algorithm of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023].