On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication

We study connections between the problem of fully dynamic <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-\epsilon)$</tex>-approximate maximum bipartite matching, and the dual <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+\epsilon)$</tex>-approximate vertex cover problem, with the online matrix-vector (OMv) conjecture which has recently been used in several fine-grained hardness reductions. We prove that there is an online algorithm that maintains a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+\epsilon)$</tex>-approximate vertex cover in amortized <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{1-c}\epsilon^{-C}$</tex> time for constants <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$c, C &gt; 0$</tex> for fully dynamic updates if and only if the OMv conjecture is false. Similarly, we prove that there is an online algorithm that maintains a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-\epsilon)$</tex>-approximate maximum matching in amortized <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{1-c}\epsilon^{-C}$</tex> time if and only if there is a nontrivial algorithm for another dynamic problem, which we call dynamic approximate OMv, that has seemingly no matching structure. This provides some evidence against achieving amortized sublinear update times for approximate fully dynamic matching and vertex cover. Leveraging these connections, we obtain faster algorithms for approximate fully dynamic matching in both the online and offline settings. We give a randomized algorithm that with high probability maintains a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1-\epsilon)$</tex>-approximate bipartite matching and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+\epsilon)$</tex>-approximate vertex cover in fully dynamic graphs, in amortized <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\epsilon^{-O(1)}\frac{n}{2^{\Omega}(\sqrt{\log n})})$</tex> up-date time. This improves over the previous fastest runtimes of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n/(\log^{*}n)^{\Omega(1)})$</tex> due to Assadi-Behnezhad-Khanna-Li [STOC 2023], and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O_{\epsilon}(n^{1-\Omega_{\epsilon}(1)})$</tex> due to Bhattacharya-Kiss-Saranurak [FOCS 2023] for small <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon$</tex>. Our algorithm leverages fast algorithms for OMv due to Larsen and Williams [SODA 2017]. We give a randomized offline algorithm for (1 - <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\epsilon)$</tex>-approximate maximum matching with amortized runtime <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{.58}\epsilon^{-O(1)})$</tex> by using fast matrix multi-plication, significantly improving over the runtimes achieved via online algorithms mentioned above. This mirrors the situation with OMv, where an offline algorithm exactly corresponds to fast matrix mul-tiplication. We also give an offline algorithm that maintains a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+\epsilon)$</tex>-approximate vertex cover in amortized <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{.723}\epsilon^{-O(1)})$</tex> time.