Search

In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a $(1-\epsilon)$-approximation of maximum matching with amortized update time potentially much better than the trivial $O(n)$ update time. The runtime of the BG algorithm is parameterized via the following graph theoretical concept: * For any $n$, define $ORS(n)$ -- standing for Ordered RS Graph -- to be the largest number of edge-disjoint matchings $M_1,\ldots,M_t$ of size $\Theta(n)$ in an $n$-vertex graph such that for every $i \in [t]$, $M_i$ is an induced matching in the subgraph $M_{i} \cup M_{i+1} \cup \ldots \cup M_t$. Then, for any fixed $\epsilon > 0$, the BG algorithm runs in \[ O\left( \sqrt{n^{1+O(\epsilon)} \cdot ORS(n)} \right) \] amortized update time with high probability, even against an adaptive adversary. $ORS(n)$ is a close variant of a more well-known quantity regarding RS graphs (which require every matching to be induced regardless of the ordering). It is currently only known that $n^{o(1)} \leqslant ORS(n) \leqslant n^{1-o(1)}$, and closing this gap appears to be a notoriously challenging problem. In this work, we further strengthen the result of Behnezhad and Ghafari and push it to limit to obtain a randomized algorithm with amortized update time of \[ n^{o(1)} \cdot ORS(n) \] with high probability, even against an adaptive adversary. In the limit, i.e., if current lower bounds for $ORS(n) = n^{o(1)}$ are almost optimal, our algorithm achieves an $n^{o(1)}$ update time for $(1-\epsilon)$-approximation of maximum matching, almost fully resolving this fundamental question. In its current stage also, this fully reduces the algorithmic problem of designing dynamic matching algorithms to a purely combinatorial problem of upper bounding $ORS(n)$ with no algorithmic considerations., Comment: 24 pages, 2 figures. In SODA 2025

We study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings -- a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contribution is a surprisingly simple deterministic rounding algorithm in bipartite graphs with amortized update time $O(\epsilon^{-1} \log^2 (\epsilon^{-1} \cdot n))$, matching an (unconditional) recourse lower bound of $\Omega(\epsilon^{-1})$ up to logarithmic factors. Moreover, this algorithm's update time improves provided the minimum (non-zero) weight in the fractional matching is lower bounded throughout. Combining this algorithm with novel dynamic \emph{partial rounding} algorithms to increase this minimum weight, we obtain several algorithms that improve this dependence on $n$. For example, we give a high-probability randomized algorithm with $\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptive adversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmic factors in the argument, i.e., $\tilde{O}(f)=O(f\cdot \mathrm{poly}(\log f))$.) Using our rounding algorithms, we also round known $(1-\epsilon)$-decremental fractional bipartite matching algorithms with no asymptotic overhead, thus improving on state-of-the-art algorithms for the decremental bipartite matching problem. Further, we provide extensions of our results to general graphs and to maintaining almost-maximal matchings., Comment: Full version of STOC 2024 paper

In the dynamic approximate maximum bipartite matching problem we are given bipartite graph $G$ undergoing updates and our goal is to maintain a matching of $G$ which is large compared the maximum matching size $\mu(G)$. We define a dynamic matching algorithm to be $\alpha$ (respectively $(\alpha, \beta)$)-approximate if it maintains matching $M$ such that at all times $|M | \geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha - \beta$). We present the first deterministic $(1-\epsilon )$-approximate dynamic matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for graphs undergoing edge insertions. Previous solutions either required super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or exponential in $1/\epsilon $ [Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our implementation is arguably simpler than the mentioned algorithms and its description is self contained. Moreover, we show that if we allow for additive $(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also handle vertex deletions, on top of edge insertions. This makes our algorithm one of the few small update time algorithms for $(1-\epsilon )$-approximate dynamic matching allowing for updates both increasing and decreasing the maximum matching size of $G$ in a fully dynamic manner.

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate \emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for $(1,\epsilon n)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least $1.499$ or assumed that the graph has a very small maximum degree.

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation factor of $2$. Very recently, Behnezhad et al.[SODA'23] improved the approximation factor to $(2-\frac{1}{2^{O(1/\gamma)}})$ using $n^{1+\gamma}$ time. This improvement over the factor $2$ is, however, minuscule and they asked if even $1.99$-approximation is possible in $n^{2-\Omega(1)}$ time. We give a strong affirmative answer to this open problem by showing $(1.5+\epsilon)$-approximation algorithms that run in $n^{2-\Theta(\epsilon^{2})}$ time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and streaming [Bernstein ICALP'20] settings, but never before in the sublinear setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23] independently showed sublinear algorithms similar to our Theorem 1.2 in both adjacency list and matrix models. Furthermore, in [BRR'23], they show additional results on strictly better-than-1.5 approximate matching algorithms in both upper and lower bound sides.

In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g., [Gupta et al. STOC'17; Arar et al. ICALP'18, Wajc STOC'20]) has been devoted to the study of special cases of dynamic packing and covering LPs, such as the dynamic fractional matching and set cover problems. But until now, there is no non-trivial dynamic algorithm for general packing and covering LPs. In this paper, we settle the complexity of dynamic packing and covering LPs, up to a polylogarithmic factor in update time. More precisely, in the partially dynamic setting (where updates can either only relax or only restrict the feasible region), we give near-optimal deterministic $\epsilon$-approximation algorithms with polylogarithmic amortized update time. Then, we show that both partially dynamic updates and amortized update time are necessary; without any of these conditions, the trivial algorithm that recomputes the solution from scratch after every update is essentially the best possible, assuming SETH. To obtain our results, we initiate a systematic study of the multiplicative weights update (MWU) method in the dynamic setting. As by-products of our techniques, we also obtain the first online $(1+\epsilon)$-competitive algorithms for both covering and packing LPs with polylogarithmic recourse, and the first streaming algorithms for covering and packing LPs with linear space and polylogarithmic passes.

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than $2$. Specifically, we obtain a $1+\frac{1}{\sqrt{2}}+\epsilon\approx 1.707+\epsilon$ approximation in bipartite graphs and a $1.973+\epsilon$ approximation in general graphs. We thus answer in the affirmative the major open question first posed in the influential work of Onak and Rubinfeld (STOC'10) and repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms also work against an adaptive adversary and guarantee worst-case polylog update time, both w.h.p. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier., Comment: Full version of SODA 2023 paper

We present deterministic algorithms for maintaining a $(3/2 + \epsilon)$ and $(2 + \epsilon)$-approximate maximum matching in a fully dynamic graph with worst-case update times $\hat{O}(\sqrt{n})$ and $\tilde{O}(1)$ respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio $(2 - \delta)$ (for any $\delta > 0$) and $(2 + \epsilon)$ were both shown by Roghani et al. [2021] with update times $O(n^{3/4})$ and $O_\epsilon(\sqrt{n})$ respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are $O_\epsilon(\sqrt{n})$ and $\tilde{O}(1)$ which were shown in Bernstein and Stein [SODA'2021] and Bhattacharya and Kiss [ICALP'2021] respectively. In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC'2017] and Bernstein et al. [arXiv'2020] which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. \textbf{Independent Work:} Independently and concurrently to our work Grandoni et al. [arXiv'2021] has presented a fully dynamic algorithm for maintaining a $(3/2 + \epsilon)$-approximate maximum matching with deterministic worst-case update time $O_\epsilon(\sqrt{n})$.

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 algorithm 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. [STOC'16], Bernstein et al. [FOCS'20], and Bhattacharya and Kulkarni [SODA'19]. Prior to our work, there were two known general-purpose rounding schemes for dynamic fractional matchings. Both these schemes, by Arar et al. [ICALP'18] and Wajc [STOC'20], 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 [SODA'16] 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., Comment: An extended abstract of this paper will appear in ICALP 2021