2024/02/19 by Tuukka Korhonen, Korhonen, Tuukka, Marek Sokołowski +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2402.12364
openalex publication_date 2024/02/19 · openalex created_date 2024/02/21 · openalex updated_date 2026/07/28
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]. 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 Ok(2√(log n) log log n). The data structure furthermore can maintain whether G satisfies some fixed \sf CMSO1 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 CMSO1 sentence and vertex labels, in amortized Ok(|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].