Lune

SODA2024Top-tier venue

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

Tuukka Korhonen, Wojciech Nadara, Michal Pilipczuk, Marek Sokolowski

Abstract

The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems -Maximum Weight Independent Set and Minimum Weight Dominating Set -and we prove the following: for a fully dynamic n-vertex planar graph G, one can

• maintain a (1 -ε)-approximation of the maximum weight of an independent set in G with amortized update time f (ε) • n o(1) ; and, • under the additional assumption that the maximum degree of the graph is bounded at all times by a constant, also maintain a (1 + ε)-approximation of the minimum weight of a dominating set in G with amortized update time f (ε) • n o(1) . In both cases, f (ε) is doubly-exponential in poly(1/ε) and the data structure can be initialized in time f (ε) • n 1+o(1) . All our results in fact hold in the larger generality of any graph class that excludes a fixed apex-graph as a minor.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Dynamic Treewidth in Logarithmic Time cites A Single-Exponential Time 2-Approximation Algorithm for Treewidth
  • Dynamic Treewidth in Logarithmic Time cites Dynamic Meta-Kernelization
  • Dynamic Meta-Kernelization cites Dynamic Treewidth in Logarithmic Time
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. The Structural Complexity of Matrix-Vector MultiplicationEmile Anand, Jan van den Brand, Rose McCartyNeurIPS 2025 · 12 citations
  2. Dynamic Treewidth in Logarithmic TimeTuukka KorhonenFOCS 2025 · 4 citations
  3. Dynamic Meta-KernelizationChristian Bertram, Deborah Haun, Mads Vestergaard Jensen, Tuukka KorhonenSTOC 2026 · 2 citations
  4. A Graph Minors Approach to Temporal SequencesJohannes Carmesin, Will J. TurnerSTOC 2026 · 1 citation

Builds on2

  1. A Single-Exponential Time 2-Approximation Algorithm for TreewidthTuukka KorhonenFOCS 2021 · 49 citations
  2. Baker game and polynomial-time approximation schemesZdenek DvorákSODA 2020 · 4 citations

Related papers

  1. New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCSSoheil Behnezhad, Sanjeev KhannaSODA 2022 · 11 citations
  2. Fully-dynamic planarity testing in polylogarithmic timeJacob Holm, Eva RotenbergSTOC 2020
  3. Dynamic Approximate Maximum Independent Set on Massive GraphsXiangyu Gao, Jianzhong Li, Dongjing MiaoICDE 2022 · 5 citations
  4. Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar GraphsArnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst GutenbergFOCS 2024
  5. Deterministic Dynamic Edge ColouringAleksander B. G. ChristiansenSODA 2026
Dusk over the sea between two cliffs drawn in fine vertical lines