DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.119

Deterministic Monotone Min-Plus Product and Convolution

Authors: Ce Jin, Jaewoo Park, Barna Saha, and Yinzhan Xu

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

Abstract

The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. It also generalizes various other structured Min-Plus products studied in the literature, such as Bounded Difference Min-Plus Product and Bounded Integer Min-Plus Product. In this problem, we are given two n× n integer matrices A and B, where each row of B is a monotone non-decreasing sequence of integers from {1,…,n}, and the goal is to compute their Min-Plus product, defined as the n× n matrix C with C_{i,j} = min_k {A_{i,k} + B_{k,j}}. The fastest known algorithm for this task [Chi, Duan, Xie, and Zhang, STOC'22] runs in n^{(ω+3)/2 + o(1)} = 𝒪(n^2.686) time, significantly improving over the brute-force cubic algorithm. However, its main disadvantage is that it requires randomization, which is then inherited by all downstream applications. Our main result is a deterministic algorithm for Monotone Min-Plus product with the same running time n^{(ω+3)/2 + o(1)} = 𝒪(n^2.686) as its randomized counterpart, improving upon the previous deterministic bound 𝒪(n^{2.875}) [Gu, Polak, Vassilevska Williams, and Xu, ICALP'21]. Our derandomization also applies to previously studied extensions and variants (e.g., [Dürr, IPL'23]), including rectangular matrices, bounded range [n^μ], and column-monotone matrices. As an immediate consequence, we derandomize state-of-the-art algorithms for multiple problems, including Language Edit Distance, RNA Folding, Optimum Stack Generation, unweighted Tree Edit Distance, Batched Range Mode, and Approximate All-Pairs Shortest Paths. Our techniques also yield a deterministic algorithm for the Monotone Min-Plus Convolution problem that runs in n^{1.5 + o(1)} time, nearly matching the best-known randomized time complexity 𝒪̃(n^1.5) [Chi, Duan, Xie, and Zhang, STOC'22]. This algorithm can be used to derandomize state-of-the-art algorithms for Jumbled Indexing for binary strings and several variants of Knapsack.

Cite as

Ce Jin, Jaewoo Park, Barna Saha, and Yinzhan Xu. Deterministic Monotone Min-Plus Product and Convolution. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 119:1-119:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ICALP.2026.119,
  author =	{Jin, Ce and Park, Jaewoo and Saha, Barna and Xu, Yinzhan},
  title =	{{Deterministic Monotone Min-Plus Product and Convolution}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{119:1--119:23},
  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.119},
  URN =		{urn:nbn:de:0030-drops-265085},
  doi =		{10.4230/LIPIcs.ICALP.2026.119},
  annote =	{Keywords: Min-plus product, min-plus convolution, monotone matrices, fine-grained complexity, deterministic algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.87

Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time

Authors: Kevin Hua, Daniel Li, Jaewoo Park, and Thatchaphol Saranurak

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected components (also known as shredders) and for finding the most shattering one, i.e., the one maximizing the number of connected components. Our algorithms break the quadratic time bound by Cheriyan and Thurimella (STOC'96) for both problems that has been unimproved for more than two decades. Our work also removes an important bottleneck to near-linear time algorithms for the vertex connectivity augmentation problem (Jordan '95) and finding an even-length directed cycle in a graph, a problem shown to be equivalent to many other fundamental problems (Vazirani and Yannakakis '90, Robertson et al. '99). Note that it is necessary to list only minimum vertex cuts that separate the graph into at least three components because there can be an exponential number of minimum vertex cuts in general. To obtain a near-linear time algorithm, we have extended techniques in local flow algorithms developed by Forster et al. (SODA'20) to list shredders on a local scale. We also exploit fast queries to a pairwise vertex connectivity oracle subject to vertex failures (Long and Saranurak FOCS'22, Kosinas ESA'23). This is the first application of using connectivity oracles subject to vertex failures to speed up a static graph algorithm.

Cite as

Kevin Hua, Daniel Li, Jaewoo Park, and Thatchaphol Saranurak. Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hua_et_al:LIPIcs.ICALP.2024.87,
  author =	{Hua, Kevin and Li, Daniel and Park, Jaewoo and Saranurak, Thatchaphol},
  title =	{{Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{87:1--87:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.87},
  URN =		{urn:nbn:de:0030-drops-202302},
  doi =		{10.4230/LIPIcs.ICALP.2024.87},
  annote =	{Keywords: Graphs, Flows, Randomized Algorithms, Vertex Connectivity}
}

Search Results

Documents authored by Park, Jaewoo

Deterministic Monotone Min-Plus Product and Convolution

Abstract

Cite as

Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message