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