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 4 k 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 loglog n ). The data structure furthermore can maintain whether G satisfies some fixed 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 CMSO 1 sentence and vertex labels, in amortized O k (| X | · 2 √log n loglog n ) time. Our dynamic algorithm generalizes the dynamic treewidth algorithm of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023].

Authors

• Tuukka Korhonen
• Marek Sokolowski 0001

Keywords

• cliquewidth
• monadic second-order logic
• parameterized complexity
• rankwidth