On the hardness of partially dynamic graph problems and connections to diameter

TY - GEN

T1 - On the hardness of partially dynamic graph problems and connections to diameter

AU - Dahlgaard, Søren

N1 - Conference code: 43

PY - 2016/8/1

Y1 - 2016/8/1

N2 - Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: No algorithm with amortized update time O(n1-ϵ) exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the O(m1/2-ϵ) bound for sparse graphs of Henzinger et al. [STOC'15] and O(n1/3-ϵ) bound of Kopelowitz, Pettie and Porat1. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time O(m√n) exists for the former by Bosek et al. [FOCS'14]. No algorithm with amortized update time O(m1-ϵ) exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time O(n1-ϵ) exists for directed and unweighted graphs or undirected and weighted graphs. No algorithm with amortized update time O(n1/2-ϵ) exists for incremental or decremental (4/3 - ϵ')-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. The result is then extended to the static case, where we show that no O((n√m)1-ϵ) algorithm exists. We also extend the result to the case when an additive error is allowed in the approximation. While our bounds are weaker than the already known bounds of Roditty and Vassilevska Williams [STOC'13], it is based on a weaker conjecture of Abboud et al. [STOC'15] and is the first known reduction from the 3SUM and APSP problems to diameter. Showing an equivalence between APSP and diameter is a major open problem in this area (Abboud et al. [SODA'15]), and thus showing even a weak connection in this direction is of interest.

AB - Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that: No algorithm with amortized update time O(n1-ϵ) exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the O(m1/2-ϵ) bound for sparse graphs of Henzinger et al. [STOC'15] and O(n1/3-ϵ) bound of Kopelowitz, Pettie and Porat1. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time O(m√n) exists for the former by Bosek et al. [FOCS'14]. No algorithm with amortized update time O(m1-ϵ) exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time O(n1-ϵ) exists for directed and unweighted graphs or undirected and weighted graphs. No algorithm with amortized update time O(n1/2-ϵ) exists for incremental or decremental (4/3 - ϵ')-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. The result is then extended to the static case, where we show that no O((n√m)1-ϵ) algorithm exists. We also extend the result to the case when an additive error is allowed in the approximation. While our bounds are weaker than the already known bounds of Roditty and Vassilevska Williams [STOC'13], it is based on a weaker conjecture of Abboud et al. [STOC'15] and is the first known reduction from the 3SUM and APSP problems to diameter. Showing an equivalence between APSP and diameter is a major open problem in this area (Abboud et al. [SODA'15]), and thus showing even a weak connection in this direction is of interest.

U2 - 10.4230/LIPIcs.ICALP.2016.48

DO - 10.4230/LIPIcs.ICALP.2016.48

M3 - Article in proceedings

T3 - Leibniz International Proceedings in Informatics

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

A2 - Chatzigiannakis, Ioannis

A2 - Mitzenmacher, Michael

A2 - Rabani, Yuval

A2 - Sangiorgi, Davide

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Colloquium on Automata, Languages, and Programming 2016

Y2 - 12 July 2016 through 15 July 2016

ER -