Skip to content
Preprint

Breaking Two Barriers for Dynamic Planar Reachability

Oct 2026 · 0 citations
Computer Science

TL;DR

The first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting is presented, obtaining time ${O}(n^{0.49})$ per query/update, which is the first improvement upon the exponent $2/3$ in over three decades.

Abstract

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{{O}}(n^{2/3})$ per query/update [Subramanian, ESA'93]. This can be improved to $\widetilde{{O}}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA'07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS'16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number''[Chazelle and Welzl, Discrete Comput. Geom.'89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

View source

Similar papers

Preprint Nov 2026

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

A randomized algorithm is given that estimates the reachability diameter of an unweighted digraph within a factor of $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time, establishing the necessity of polynomial loss for nearly-linear time algorithms.

Hector Tierno, Shuang Yang · 0 citations
#edge computing Preprint Nov 2026

Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorith...

Gary Hoppenworth, George Z. Li, S. Mahabadi et al. · 0 citations
Preprint Nov 2026

A Simple Subquadratic Cut Query Protocol for Directed Reachability

We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has posi...

Henry L. Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal · 1 citation
Preprint Oct 2026

Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators

We study the fully-dynamic all-pairs minimum cut problem on planar graphs. Given an $n$-vertex undirected planar graph $G=(V,E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates while supporting $s$-$t$ minimum cut queries for any pair of vertices $s$ and $t$. We give a $(1+\va...

Arnold Filtser, Gramoz Goranci, Ali Momeni et al. · 0 citations
Preprint Nov 2026

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining...

Prantar Ghosh, Amirhossein Janfaza · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.