We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms, we derive the following new results: (1) The first deterministic algo
rithm for maintaining a $(2-delta)$-approximate maximum matching in a fully dynamic bipartite graph, in arbitrarily small polynomial update time. (2) The first deterministic algorithm for maintaining a $(1+delta)$-approximate maximum matching in a decremental bipartite graph, in polylogarithmic update time. (3) The first deterministic algorithm for maintaining a $(2+delta)$-approximate maximum matching in a fully dynamic general graph, in small polylogarithmic (specifically, $O(log^4 n)$) update time. These results are respectively obtained by applying our framework on top of the fractional matching algorithms of Bhattacharya et al. [STOC16], Bernstein et al. [FOCS20], and Bhattacharya and Kulkarni [SODA19]. Prior to our work, there were two known general-purpose rounding schemes for dynamic fractional matchings. Both these schemes, by Arar et al. [ICALP18] and Wajc [STOC20], were randomized. Our rounding scheme works by maintaining a good {em matching-sparsifier} with bounded arboricity, and then applying the algorithm of Peleg and Solomon [SODA16] to maintain a near-optimal matching in this low arboricity graph. To the best of our knowledge, this is the first dynamic matching algorithm that works on general graphs by using an algorithm for low-arboricity graphs as a black-box subroutine. This feature of our rounding scheme might be of independent interest.
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL92] conjectured that an online $(1+o(1))Delta$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $Delta=omega(log n)$. This conjecture remains open in general, though it was re
cently proven for bipartite graphs under emph{one-sided vertex arrivals} by Cohen et al.~[FOCS19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the emph{random-order} online model. For this model, known results fall short of the Bar-Noy et al.~conjecture, either in the degree bound [Aggarwal et al.~FOCS03], or number of colors used [Bahmani et al.~SODA10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al.~conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with emph{recourse}. A recent algorithm of Duan et al.~[SODA19] yields a $(1+epsilon)Delta$-edge-coloring with poly$(log n/epsilon)$ recourse. We achieve the same with poly$(1/epsilon)$ recourse, thus removing all dependence on $n$. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rodl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al.~[TCS98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $min(O(log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of se
ts, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Omega(log n)$, this was achieved by a deterministic $O(log n)$-approximation algorithm with $O(f log n)$ amortized update time [Gupta et al. STOC17]. In the low-frequency range, the line of work by Gupta et al. [STOC17], Abboud et al. [STOC19], and Bhattacharya et al. [ICALP15, IPCO17, FOCS19] led to a deterministic $(1+epsilon)f$-approximation algorithm with $O(f log (Cn)/epsilon^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+epsilon)f$-approximation ratio in $O(flog^2 (Cn)/epsilon^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(log^3 n/text{poly}(epsilon))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA17]. 2. $(1+epsilon)f$-approximation ratio in $Oleft((f^2/epsilon^3)+(f/epsilon^2) log Cright)$ amortized update time: This result improves the previous $O(f log (Cn)/epsilon^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).
To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific problems such as the Strong Exponential Time Hypothesis (SETH) and the O
nline Matrix-Vector Multiplication Conjecture (OMv). While they have led to many exciting discoveries, dynamic algorithms still miss out some benefits and lessons from the traditional ``coarse-grained approach that relates together classes of problems such as P and NP. In this paper we initiate the study of coarse-grained complexity theory for dynamic algorithms. Below are among questions that this theory can answer. What if dynamic Orthogonal Vector (OV) is easy in the cell-probe model? A research program for proving polynomial unconditional lower bounds for dynamic OV in the cell-probe model is motivated by the fact that many conditional lower bounds can be shown via reductions from the dynamic OV problem. Since the cell-probe model is more powerful than word RAM and has historically allowed smaller upper bounds, it might turn out that dynamic OV is easy in the cell-probe model, making this research direction infeasible. Our theory implies that if this is the case, there will be very interesting algorithmic consequences: If dynamic OV can be maintained in polylogarithmic worst-case update time in the cell-probe model, then so are several important dynamic problems such as $k$-edge connectivity, $(1+epsilon)$-approximate mincut, $(1+epsilon)$-approximate matching, planar nearest neighbors, Chans subset union and 3-vs-4 diameter. The same conclusion can be made when we replace dynamic OV by, e.g., subgraph connectivity, single source reachability, Chans subset union, and 3-vs-4 diameter. Lower bounds for $k$-edge connectivity via dynamic OV? (see the full abstract in the pdf file).
The problem of (vertex) $(Delta+1)$-coloring a graph of maximum degree $Delta$ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA18, B
hattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a $(Delta+1)$-coloring with $O(log Delta)$ expected amortized update time. In this paper, we present a $(Delta+1)$-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.
We present a deterministic dynamic algorithm for maintaining a $(1+epsilon)f$-approximate minimum cost set cover with $O(flog(Cn)/epsilon^2)$ amortized update time, when the input set system is undergoing element insertions and deletions. Here, $n$ d
enotes the number of elements, each element appears in at most $f$ sets, and the cost of each set lies in the range $[1/C, 1]$. Our result, together with that of Gupta et al. [STOC`17], implies that there is a deterministic algorithm for this problem with $O(flog(Cn))$ amortized update time and $O(min(log n, f))$-approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only $O(log (Cn))$ away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was $O(f^2)$, which was due to Bhattacharya et al. [ICALP`15]. In contrast, the only result that guaranteed $O(f)$-approximation was obtained very recently by Abboud et al. [STOC`19], who designed a dynamic algorithm with $(1+epsilon)f$-approximation ratio and $O(f^2 log n/epsilon)$ amortized update time. Besides the extra $O(f)$ factor in the update time compared to our and Gupta et al.s results, the Abboud et al. algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed.
