We study dynamic algorithms for maintaining fundamental algebraic properties of matrices, specifically, rank, basis, and full-rank submatrices, with applications to maximum matching on dynamic graphs. Prior dynamic algorithms for rank achieve subquadratic update times but scale with the matrix dimension n, and could not always maintain the corresponding objects such as a basis or maximum full-rank submatrix. We present the first dynamic rank algorithms whose update time scales with the matrix rank r, achieving Õ(r^1.405) time per entry-update and Õ(r^1.528 + z) per column-update, where z is the number of changed entries. This extends to Õ(|M|^1.405) edge-update time to maintain the size |M| of a maximum matching. We also give dynamic algorithms for maintaining a column-basis subject to column-updates and a maximum full-rank submatrix subject to entry-updates.

Many iterative algorithms in computer science require repeated computation of some algebraic expression whose input varies slightly from one iteration to the next. Although efficient data structures have been proposed for maintaining the solution of such algebraic expressions under low-rank updates, most of these results are only analyzed under exact arithmetic (real-RAM model and finite fields) which may not accurately reflect the more limited complexity guarantees of real computers. In this paper, we analyze the stability and bit complexity of such data structures for expressions that involve the inversion, multiplication, addition, and subtraction of matrices under the word-RAM model. We show that the bit complexity only increases linearly in the number of matrix operations in the expression. In addition, we consider the bit complexity of maintaining the determinant of a matrix expression. We show that the required bit complexity depends on the logarithm of the condition number of matrices instead of the logarithm of their determinant. Finally, we discuss rank maintenance and its connections to determinant maintenance. Our results have wide applications ranging from computational geometry (e.g., computing the volume of a polytope) to optimization (e.g., solving linear programs using the simplex algorithm).

We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg⁡n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings in general interval graphs, we design linear space data structures that support distance queries in O(lg⁡n) worst-case time and vertex insertion or deletion in O(lg⁡n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings in general interval graphs, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(nlg⁡n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg⁡n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n)=Ω(1) and S(n)=O(n). This implies an O(n)-word solution with O(nlg⁡n)-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg⁡n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.

Since the development of efficient linear program solvers in the 80s, all major improvements for solving multi-commodity flows to high accuracy came from improvements to general linear program solvers. This differs from the single commodity problem (e.g. maximum flow) where all recent improvements also rely on graph specific techniques such as graph decompositions or the Laplacian paradigm. This phenomenon sparked research to understand why these graph techniques are unlikely to help for multi-commodity flow. [Kyng and Zhang FOCS’17] reduced solving multi-commodity Laplacians to general linear systems and [Ding, Kyng, and Zhang ICALP’22] showed that general linear programs can be reduced to 2-commodity flow. However, the reductions create sparse graph instances, so improvement to multi-commodity flows on denser graphs might exist. We show that one can indeed speed up multi-commodity flow algorithms on non-sparse graphs using graph techniques from single-commodity flow algorithms. This is the first improvement to high accuracy multi-commodity flow algorithms that does not just stem from improvements to general linear program solvers. In particular, using graph data structures from recent min-cost flow algorithm by [Brand, Lee, Liu, Saranurak, Sidford, Song, and Wang STOC’21] based on the celebrated expander decomposition framework, we show that 2-commodity flow on an n-vertex m-edge graph can be solved deterministically in $\widetilde{O}\left(\sqrt{m} n^{\omega-1 / 2}\right)$ time for current bounds on fast matrix multiplication $\omega \approx 2.372$, improving upon the previous fastest algorithms with $\widetilde{O}\left(m^{\omega}\right)$ [Cohen, Lee, and Song STOC’19] and $\widetilde{O}\left(\sqrt{m} n^{2}\right)$ [Kapoor and Vaidya;96] time complexity. For general k commodities, our algorithm runs in $\widetilde{O}\left(k^{2.5} \sqrt{m} n^{\omega-1 / 2}\right)$ time.