Marek Sokolowski 0001

STOC Conference 2025 Conference Paper

Fully Dynamic Biconnectivity in Õ(log² n) Time

• Jacob Holm
• Wojciech Nadara
• Eva Rotenberg
• Marek Sokolowski 0001

STOC Conference 2024 Conference Paper

Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth

• Tuukka Korhonen
• Marek Sokolowski 0001

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].

SODA Conference 2024 Conference Paper

Exact Shortest Paths with Rational Weights on the Word RAM

• Adam Karczmarz
• Wojciech Nadara
• Marek Sokolowski 0001

SODA Conference 2024 Conference Paper

Fully dynamic approximation schemes on planar and apex-minor-free graphs

• Tuukka Korhonen
• Wojciech Nadara
• Michal Pilipczuk
• Marek Sokolowski 0001

FOCS Conference 2023 Conference Paper

Dynamic treewidth

• Tuukka Korhonen
• Konrad Majewski
• Wojciech Nadara
• Michal Pilipczuk
• Marek Sokolowski 0001

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO 2 logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].