Source-linked AI summary
Popular conjectures imply strong lower bounds for dynamic problems
Amir Abboud, Virginia Vassilevska Williams
TL;DR
The paper asks how much dynamic algorithms can improve for several difficult problems whose efficient solutions would challenge major conjectures. It proves conditional lower bounds by reducing from five conjectured hard problems, obtaining near-optimal barriers that persist under polynomial preprocessing and, often, lookahead or partial dynamism. The results constrain progress on matching, reachability, connectivity, shortest paths, and related problems.
Problem
Many dynamic problems have no practical or substantially better algorithms, while unconditional cell-probe lower bounds remain only logarithmic rather than polynomial.
Method
The paper proves conditional lower bounds for a broad collection of dynamic problems from the 3SUM, APSP, Triangle, Boolean matrix multiplication, and SETH conjectures.
Results
Many SETH-based lower bounds achieve essentially optimal guarantees even with arbitrary polynomial preprocessing, and matching improvements would refute 3SUM, Triangle, or combinatorial Boolean matrix multiplication conjectures at stated thresholds.
Takeaways & Limitations
The results indicate that substantial improvements for these dynamic problems would imply breakthroughs on major open problems in algorithms.
Takeaways & Limitations
The decremental relationship in one triangle-based reduction is not immediately established, unlike the corresponding incremental insertion bound.
Abstract
from arXiv · showhide
We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1. Is the 3SUM problem on $n$ numbers in $O(n^{2-ε})$ time for some $ε>0$? 2. Can one determine the satisfiability of a CNF formula on $n$ variables in $O((2-ε)^n poly n)$ time for some $ε>0$? 3. Is the All Pairs Shortest Paths problem for graphs on $n$ vertices in $O(n^{3-ε})$ time for some $ε>0$? 4. Is there a linear time algorithm that detects whether a given graph contains a triangle? 5. Is there an $O(n^{3-ε})$ time combinatorial algorithm for $n\times n$ Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu [STOC 2010].
1 Introduction
Dynamic algorithms update computed values after small input changes, but several important problems remain difficult despite limited practical progress. This paper develops strong conditional lower bounds for many dynamic problems from five major conjectures, including SETH, 3SUM, APSP, Triangle, and Boolean matrix multiplication.
- Dynamic algorithms update function values after small input changes without recomputing from scratch, supporting applications including connectivity, matching, and approximate shortest paths.
- Dynamic single-source reachability, shortest paths, matching, strongly connected components, and Pagh’s problem remain difficult, with limited improvements over recomputation and sometimes impractical techniques.
- Conditional polynomial lower bounds are sought because known cell-probe lower bounds are at best logarithmic, while these problems require bounds of the form Ω(N^c).
- The paper extends prior conditional lower-bound work to a much larger collection of dynamic problems using five conjectures: 3SUM, APSP, Triangle, Boolean matrix multiplication, and SETH.
- The study is the first to relate dynamic-problem complexity to exact Boolean Satisfiability complexity via SETH, including randomized fully dynamic algorithms with expected amortized update times.
- Many SETH-based lower bounds remain valid with arbitrary polynomial preprocessing, while most results also apply to partially dynamic algorithms with worst-case bounds and lookahead.
2 Prior work and our results
The paper develops conditional lower bounds for many dynamic problems, tying substantial improvements to breakthroughs in 3SUM, APSP, triangle detection, Boolean matrix multiplication, or SETH-based SAT algorithms. Results cover matching, reachability, shortest paths, connectivity, and related problems, often showing that trivial or existing bounds are essentially optimal under these conjectures.
- Matching: Dynamic maximum bipartite matching with update and query time O(m^ε) for ε < 1 would have consequences for triangle detection, 3SUM, and combinatorial Boolean matrix multiplication.The thresholds are ε < 0.81 for improving sparse triangle detection, ε < 1/3 for truly subquadratic 3SUM, and any ε < 1 for combinatorial BMM.
- Matching: Any dynamic maximum weight matching algorithm with amortized update time O(n^(2−ε)) in dense graphs would imply a truly subcubic APSP algorithm.This applies even to incremental or decremental algorithms.
- Subgraph connectivity: Under the 3SUM conjecture, SubConn requires either preprocessing time O(m^(4/3−ε)) to be impossible or a tradeoff between update and query times.Specifically, preprocessing O(m^(4/3−ε)), update O(m^α), and query O(m^(2/3−α−ε)) cannot all hold for ε > 0 and 1/6 < α < 1/3.
- Reachability and connectivity: Conditional lower bounds make trivial recomputation essentially optimal for several connectivity and reachability variants.These include ConnSub under SETH, #SSR under SETH, and SC2 under SETH; combinatorial ss-Reach also requires m^(1−o(1)) worst-case update or query time under the BMM conjecture.
- Reachability and shortest paths: For dynamic st-Reach and related shortest-path problems, the conjectures impose strong preprocessing or update/query-time barriers.Under 3SUM, st-Reach requires preprocessing m^(4/3−o(1)) or update/query m^(1/3−o(1)); under BMM, truly subcubic preprocessing with truly subquadratic updates and queries would yield truly subcubic BMM.
3 Description of our techniques
The paper develops conditional lower bounds through reductions from SETH, Triangle Detection, BMM, and 3SUM. These constructions encode assignments, paths, and set intersections into dynamic problems, transferring improvements in dynamic algorithms to faster algorithms for the conjectured-hard problems.
- Lower bounds based on the SETH: SETH reductions split variables into two halves, represent partial assignments and clauses as graph nodes, and encode satisfiability through reachability.A formula is satisfiable exactly when some assignment pair is not connected by the constructed directed paths.
- Lower bounds based on the SETH: Dynamic counting reachability replaces all partial-assignment nodes with one source and processes assignments in stages using selective edge insertions.The construction performs O(n2^(n/2)) updates and O(2^(n/2)) queries on a graph with N = O(2^(n/2)) vertices and m = O(n2^(n/2)) edges.
- Lower bounds based on the SETH: Allowing polynomial preprocessing does not evade the SETH reduction: unbalanced variable splits keep preprocessing subexponential while dynamic operations still yield a faster SAT algorithm.The construction uses parts of sizes (1−δ)n and δn, with δ chosen below the preprocessing exponent's reciprocal.
- Lower bounds from Triangle Detection and BMM: Triangle reductions create four vertex copies and encode triangles as paths from uA to uD, then use staged source-target queries to test each vertex.The resulting graph has O(m) edges and O(n) vertices, while the staged construction uses O(n) updates and queries overall.
- Lower bounds from Triangle Detection and BMM: Reductions from st-Reach transfer preprocessing, update, and query bounds to Strong Connectivity and Bipartite Perfect Matching, while a separate reduction handles subgraph connectivity.For Pagh's problem, the paper instead uses high-degree vertices, set intersections, and a complementary low-degree case.
- Lower bounds from 3SUM: The 3SUM approach directly reduces Patrascu's triangle-listing construction to dynamic problems, avoiding inefficiencies of the intermediate multiphase problem.Known reductions from triangle listing to triangle finding are insufficient for the needed subquadratic 3SUM consequence, motivating a direct treatment.
4 The conjectures
The paper reviews conjectured hardness for 3SUM, APSP, CNF-SAT, triangle detection, and Boolean matrix multiplication, and uses these conjectures as foundations for dynamic lower bounds.
- 3SUM: 3SUM asks whether three integers satisfy a+b=c, with no known O(n^{2-ε}) algorithm for any ε>0.The conjecture requires n^{2-o(1)} expected time in the Word RAM model for bounded integers.
- APSP: APSP computes all-pairs distances, and the paper conjectures that weighted n-node graphs require n^{3-o(1)} expected time.Many other graph problems are related to APSP through subcubic reductions.
- SETH: SETH conjectures that for every ε>0, some k-SAT requires O(2^{(1-ε)n} poly n) time to solve.The best general CNF-SAT algorithm remains exhaustive search in O*(2^n) time, while fixed-k algorithms approach base 2 as k grows.
- Triangle detection: Triangle detection is conjectured to require m^{1+δ-o(1)} expected time for some constant δ>0, rather than linear time.The best known methods rely on fast matrix multiplication, motivating the conjecture.
- Boolean matrix multiplication: The paper also highlights Boolean matrix multiplication because many important problems are solved using, or are equivalent to, fast BMM.Dense triangle detection and BMM have a known relationship, while the relationship between triangle detection and APSP is comparatively loose.
5 Formal statement of our results
The formal results give conditional thresholds for dynamic graph and set problems: sufficiently fast update, query, or preprocessing bounds would refute 3SUM, SETH, triangle, APSP, or combinatorial BMM conjectures.
- SETH-based results: Under SETH, subpolynomial improvements to listed dynamic problems would refute SETH through bounds summarized in Theorem 5.1.The theorem covers fully dynamic and partially dynamic variants with specified preprocessing and update/query exponents.
- Triangle-based results: Under the triangle conjecture, sufficiently fast dynamic st-Reach, BPMatch, BPM variants, SC, st-SubConn, or PP variants would imply a faster triangle algorithm.The thresholds depend on δ, the conjectured exponent gap for triangle detection.
- 3SUM-based results: Under the 3SUM conjecture, improved incremental or decremental st-Reach, BPMatch, SC, or PP variants would falsify Conjecture 1.The theorem specifies preprocessing O(m^{4...}) bounds in the supplied statement.
- Combinatorial BMM results: Under the combinatorial BMM conjecture, fast dynamic reachability, matching, connectivity, subconnectivity, and set problems would falsify Conjecture 5.The listed consequences include preprocessing O(n^{3-ε}) and problem-dependent update/query thresholds.
- APSP-based results: Under the APSP conjecture, incremental or decremental single-source shortest paths or bipartite weighted matching with the stated bounds would falsify Conjecture 2.The theorem uses preprocessing O(n^{3-ε}) and amortized update and query times O(n^{2-ε}).
6 Preliminaries
The preliminaries establish reductions that transfer dynamic algorithms between connectivity, reachability, matching, and shortest-path problems while preserving complexity up to graph-size changes.
- Connectivity and reachability: st-SubConn reduces to directed st-Reach by splitting every vertex into in and out copies and activating vertices through internal edges.The constructed graph has O(n) nodes and O(m+n) edges, and connectivity corresponds to reachability from s_out to t_in.
- Matching reductions: st-Reach reduces to bipartite perfect matching: the constructed graph has a perfect matching exactly when an s-to-t path exists.Edge updates in the original graph are represented by corresponding bipartite-edge updates.
- Shortest paths: Weighted bipartite matching encodes shortest paths by assigning weight M to copy edges and M-w(u,v) to graph edges.The maximum matching value equals n·M minus the shortest-path weight.
- Strong connectivity: Strong connectivity can encode s-to-t reachability by adding edges from every nonterminal vertex to s and from t to every nonterminal vertex.The resulting graph is strongly connected exactly when the original graph contains an s-to-t path.
- Set and connectivity problems: SubUnion reduces efficiently to ConnSub, connecting the dynamic set problem to subgraph connectivity.The paper uses this relationship to derive further conditional lower bounds.
7 Lower bounds from SETH
The SETH reductions encode CNF-SAT into dynamic instances with exponentially many stages, yielding near-polynomial conditional lower bounds for reachability, connectivity, SCC, diameter, and set problems.
- Quadratic-scale lower bounds: SETH implies max{u(n),q(n)}≥Ω(n^{2-ε}) for fully dynamic ST-Reach and (4/3)-approximate diameter.The bound also holds for incremental and decremental variants with worst-case times.
- Lower bounds near n: SETH implies that sparse fully dynamic #SSR, SC2, AppxSCC, MaxSCC, SubUnion, φ-PP, and ConnSub require max{u(n),q(n)}≥Ω(n^{1-ε}).The same exponent applies to incremental and decremental variants under worst-case update and query times.
- Reduction framework: The reductions start from H_δ, add only constantly many nodes and O(n) edges, and choose δ=(1-ε)/t to control preprocessing.This preserves near-linear graph size while making preprocessing compatible with the SETH contradiction.
- Reduction framework: The constructions use 2^{(1-δ)n} stages, each with O(n) updates and O(n) queries, to simulate CNF-SAT.Assuming sufficiently fast dynamic operations would solve CNF-SAT faster than permitted by SETH.
- Set and connectivity lower bounds: The set-problem reductions establish matching Ω(n^{1-ε}) lower bounds for fully dynamic and partially dynamic ConnSub, SubUnion, and ∅-PP.The ConnSub result follows from the efficient SubUnion-to-ConnSub reduction.
8 Lower bounds from Triangle
The paper reduces Triangle detection to several dynamic problems, yielding conditional lower bounds for update, query, and preprocessing times under Triangle hardness.
- Triangle detection reduces to fully dynamic st-Reach with preprocessing p(m,n), update u(m,n), and query q(m,n) in O(n(u(m,n)+q(m,n))+p(m,n)) time.
- The same reduction extends to decremental st-Reach with worst-case update and query times, preserving the O(n(u(m,n)+q(m,n))+p(m,n)) bound.
- If BPMatch, st-Reach, or SC achieve u(m,n),q(m,n)≤O(m^ε), Triangle detection would run in O(m^(1+ε/2)) time.
- O(m) updates and n queries suffice for Triangle detection through st-SubConn, while decremental st-SubConn requires O(n^2) updates and n queries.
- Dynamic ∅-PP with k=O(m) subsets yields Triangle detection in O(p(n,k)+m(u(n,k)+q(n,k))) time.
- Triangle reductions also apply directly to dynamic matching: 5-BPM uses O(m) updates and n queries, while 17-BPM uses O(n) updates and queries.
9 Lower bounds from APSP
The APSP section strengthens prior reductions by connecting minimum-weight triangle detection to dynamic s,t-shortest paths and bipartite maximum-weight matching with only O(n) updates and queries.
- Incremental or decremental st-SP or BPWMatch with O(n^(3−ε)) preprocessing and O(n^(2−ε)) amortized updates and queries would refute the APSP conjecture.
- Compared with prior SSSP reductions using O(n^2) queries, the paper reduces query complexity to O(n) and targets the at-least-as-easy st-SP problem.
- Minimum-weight triangle detection reduces to O(n) updates and queries of incremental or decremental st-SP on graphs with O(n) nodes and O(m) edges.
- The construction uses a four-partite graph with weighted copies of the input vertices, plus source and sink edges encoding vertex indices.
- The reduction has O(n) total updates and queries, O(n) constructed nodes, and O(m) constructed edges.
- Minimum-weight triangle detection also reduces to O(n) updates and queries of incremental or decremental BWMatch on graphs with O(n) nodes and O(m+n) edges.
10 Lower bounds from 3SUM
The paper gives direct reductions from triangle listing to dynamic problems, deriving explicit conditional tradeoffs and lower bounds from the 3SUM conjecture.
- Direct reductions bypass the multiphase problem and support explicit lower bounds for dynamic st-SubConn, st-Reach, BPMatch, and SC.
- If triangle-participating pairs can be listed in O(n^(2−ε)) time, then 3SUM admits a truly subquadratic algorithm.
- The reductions can be offline, because the dynamic algorithms may see the update and query sequence in advance.
- Using fewer queries creates a tradeoff: lower update time requires higher query time.
- For 1/6≤α≤1/3, fully dynamic st-SubConn, st-Reach, BPMatch, and SC must incur explicit polynomial update, query, or preprocessing costs unless 3SUM is truly subquadratic.