DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.45

Dynamic Rank, Basis, and Matching

Authors: Jan van den Brand, Vishal Kumar, and Daniel J. Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Jan van den Brand, Vishal Kumar, and Daniel J. Zhang. Dynamic Rank, Basis, and Matching. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 45:1-45:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vandenbrand_et_al:LIPIcs.ICALP.2026.45,
  author =	{van den Brand, Jan and Kumar, Vishal and Zhang, Daniel J.},
  title =	{{Dynamic Rank, Basis, and Matching}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{45:1--45:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.45},
  URN =		{urn:nbn:de:0030-drops-264342},
  doi =		{10.4230/LIPIcs.ICALP.2026.45},
  annote =	{Keywords: Dynamic Graph Algorithm, Dynamic Algebraic Algorithm, Dynamic Matrix Inverse, Rank, Matching}
}

Search Results

Documents authored by Kumar, Vishal

Dynamic Rank, Basis, and Matching

Abstract

Cite as

Thanks for your feedback!

Could not send message