2982 Search Results for "*"

Document/HTML   ×
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.55
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms

Authors: Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Paweł Gawrychowski, and Tatiana Starikovskaya

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

Abstract
Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model (see also [Andoni, Krauthgamer, and Onak; FOCS 2010]). Here, one is given read-only access to a (typically short) reference string R of length m, while a (typically long) text T arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression, a popular scheme for measuring and exploiting redundancy in repetitive text collections. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) T that occurs in R. Let τ be a parameter that denotes the size of the data structure. A straightforward approach maintains the data structure in {O}(m/τ) time per arriving symbol of T. We drastically improve this tradeoff and reveal fundamental barriers via a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography: - By leveraging Fiat and Naor’s function inversion data structure [SIAM J. Comput. 2000], we achieve Õ(1+m³/τ⁶) update time. In particular, for τ = √m, we obtain Õ(1) update time, improving over the Ω(√m) bound of the straightforward solution. - We establish an unconditional Ω̃(m/τ³) lower bound on the update time. Additionally, we show that achieving update time o(m³/τ⁷) would imply a breakthrough in function inversion. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.
Cite as

Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Paweł Gawrychowski, and Tatiana Starikovskaya. Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 55:1-55:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.ICALP.2026.55,
  author =	{Charalampopoulos, Panagiotis and El Ghazi, Taha and Ellert, Jonas and Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  title =	{{Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{55:1--55:20},
  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.55},
  URN =		{urn:nbn:de:0030-drops-264440},
  doi =		{10.4230/LIPIcs.ICALP.2026.55},
  annote =	{Keywords: streaming algorithms, function inversion, string algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.52
Witness-Sensitive Detection of Induced Diamonds

Authors: Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams, and Nathan Wallheimer

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

Abstract
We provide a fast witness-sensitive algorithm for detecting an induced diamond (a K₄ minus an edge) in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^2.425/t^0.25 + n², n^ω)) with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time O(n^ω log n) [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever t ≥ n^{(3-ω)/3}, where ω < 2.372 is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is r-heavy if this size is at least r, and we provide a fast detection algorithm for r-heavy diamonds in Õ(r⋅(n/r)^ω + (n/r)³+ nr) time. When there are no r-heavy diamonds, we provide a different fast detection algorithm in Õ(MM(n,n,n√{r/t})) time, where MM(a,b,c) denotes the time to multiply an a × b matrix by a b × c matrix, which is conditionally optimal for r = Õ(1). Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no r-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for 4-SUM and for a special case of 4-cycles.
Cite as

Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams, and Nathan Wallheimer. Witness-Sensitive Detection of Induced Diamonds. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2026.52,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia and Wallheimer, Nathan},
  title =	{{Witness-Sensitive Detection of Induced Diamonds}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{52:1--52:22},
  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.52},
  URN =		{urn:nbn:de:0030-drops-264419},
  doi =		{10.4230/LIPIcs.ICALP.2026.52},
  annote =	{Keywords: Induced diamond detection, Witness-sensitive algorithms, Matrix multiplication, Subgraph detection, Fine-grained complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.49
A Scalable and Unified Framework to Weighted Rank Aggregation

Authors: Amir Carmel, Debarati Das, and Tien-Long Nguyen

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

Abstract
The rank aggregation problem, seeks to combine multiple rank orderings of the same set of candidates into a single consensus ordering. Such problems arise in diverse domains, including web search, employment, college admissions, and voting. In this work we focus on the 1-median objective: given a set of m rankings over [n], the goal is to compute a ranking that minimizes the sum of its distances to all input rankings. We study rank aggregation under several classical distance metrics: Ulam distance, Spearman’s footrule, Hamming distance, and Kendall-tau, as well as their weighted variants. Our contributions begin with a novel unified framework that identifies a key structural property: it suffices to focus on a small subset of rankings (of size three or five), where the corresponding local one-median provides a good approximation to the global median. This principle extends across these distance measures, yielding a general algorithmic framework for weighted rank aggregation. Building on this, we present a new approximation algorithm for rank aggregation under the Ulam distance that scales in the Massively Parallel Computation (MPC) model. Our algorithm computes a (2-α)-approximation, for a constant α > 0, to the 1-median in a constant number of rounds, using local memory sublinear in n (the size of a ranking) and total memory near linear in n. We further design new MPC approximation algorithms for Spearman’s footrule and for the element-weighted variants of Hamming and Kendall-tau distances. For each metric, we obtain a (2-ζ)-approximation, for a constant ζ > 0 (which may differ across metrics), to the 1-median in a constant number of rounds, using local memory sublinear in n and total memory linear or near-linear in n. Moreover, for the Ulam distance, where computing the 1-median is NP-hard [Fischer et al., ESA, 2025], we simplify and strengthen the analysis of Chakraborty et al. [ITCS 2023], obtaining an improved 1.968-approximation that further extends to the weighted setting.
Cite as

Amir Carmel, Debarati Das, and Tien-Long Nguyen. A Scalable and Unified Framework to Weighted Rank Aggregation. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 49:1-49:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.ICALP.2026.49,
  author =	{Carmel, Amir and Das, Debarati and Nguyen, Tien-Long},
  title =	{{A Scalable and Unified Framework to Weighted Rank Aggregation}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{49:1--49: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.49},
  URN =		{urn:nbn:de:0030-drops-264385},
  doi =		{10.4230/LIPIcs.ICALP.2026.49},
  annote =	{Keywords: Rank aggregation, 1-median, Ulam distance, Spearman’s footrule, Kendall-tau, Hamming distance, weighted metrics, Massively Parallel Computation, Gromov product}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.48
Static to Dynamic Correlation Clustering

Authors: Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang

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

Abstract
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear 1.485-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25] , we get an 1.485-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is an 1.485-approximation with constant probability when we reach this update. Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around 3 in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] handles an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.
Cite as

Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Static to Dynamic Correlation Clustering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 48:1-48:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICALP.2026.48,
  author =	{Cao, Nairen and Cohen-Addad, Vincent and Lee, Euiwoong and Li, Shi and Lolck, David Rasmussen and Newman, Alantha and Thorup, Mikkel and Vogl, Lukas and Yan, Shuyi and Zhang, Hanwen},
  title =	{{Static to Dynamic Correlation Clustering}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-264378},
  doi =		{10.4230/LIPIcs.ICALP.2026.48},
  annote =	{Keywords: Dynamic Algorithms, Correlation Clustering, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.50
Touring a Sequence of Orthogonal Polygons

Authors: Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S.K. Lamme, Eunjin Oh, and Yanheng Wang

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

Abstract
We study the problem of computing a shortest tour that visits a sequence of k polygons P₁,…,P_k with a total number of n vertices. A tour is an oriented curve such that there exist points p_i ∈ P_i for all i where p_i appears not after p_{i+1}. In a seminal paper, Dror, Efrat, Lubiw and Mitchell (STOC 2003) considered the problem under L₂ distance, and gave Õ(nk) and Õ(nk²) algorithms for disjoint and intersecting convex polygons, respectively. In this paper, we consider the orthogonal setting (with orthogonal polygons and Manhattan distance) and obtain the following results: - a truly subquadratic Õ(n^{2-1/48}) algorithm when consecutive polygons in the sequence are disjoint; - an Õ(n) algorithm for ortho-convex polygons when consecutive polygons are disjoint; - an O(n) algorithm for axis-aligned rectangles; - Õ(n²) and Õ(n^{1.5}k²) algorithms without restrictions. Our algorithms build on a wide range of techniques, including additively weighted Voronoi diagrams, rectangle decompositions, persistent data structures, and dynamic distance oracles for weighted planar graphs.
Cite as

Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S.K. Lamme, Eunjin Oh, and Yanheng Wang. Touring a Sequence of Orthogonal Polygons. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 50:1-50:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{casel_et_al:LIPIcs.ICALP.2026.50,
  author =	{Casel, Katrin and Kisfaludi-Bak, S\'{a}ndor and Kleist, Linda and Lamme, Jeroen S.K. and Oh, Eunjin and Wang, Yanheng},
  title =	{{Touring a Sequence of Orthogonal Polygons}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{50:1--50:24},
  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.50},
  URN =		{urn:nbn:de:0030-drops-264391},
  doi =		{10.4230/LIPIcs.ICALP.2026.50},
  annote =	{Keywords: shortest path, subquadratic time, dynamic planar distance oracle}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.54
Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane

Authors: Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng

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

Abstract
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: 1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.
Cite as

Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ICALP.2026.54,
  author =	{Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, S\'{a}ndor and Le, Hung and Zheng, Da Wei},
  title =	{{Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{54:1--54:22},
  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.54},
  URN =		{urn:nbn:de:0030-drops-264432},
  doi =		{10.4230/LIPIcs.ICALP.2026.54},
  annote =	{Keywords: String graphs, Fine-grained complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.53
Hardness and Approximation for Coloring Digraphs

Authors: Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang

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

Abstract
The dichromatic number χ(D) of a digraph is the minimum number k such that V(D) can be partitioned into k subsets, each inducing an acyclic digraph. The acyclic number α(D) is the cardinality of a largest induced acyclic subdigraph of D. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating χ and α remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every ε > 0, it is hard to approximate both α and χ up to a factor of n^{1-ε} even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color 𝓁-dicolorable digraphs using at most 𝓁 ⋅ n^{1-1/(𝓁)} colors in time O(n^{2𝓁}); in particular, we can color 2-dicolorable digraphs with 2√n colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number α of the underlying graph. We consider two special cases in this regard: digraphs with χ(D) ≤ 2 and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.
Cite as

Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang. Hardness and Approximation for Coloring Digraphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2026.53,
  author =	{Chalermsook, Parinya and Gahlawat, Harmender and Klingelhoefer, Felix and Newman, Alantha and Tang, Chaoliang},
  title =	{{Hardness and Approximation for Coloring Digraphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{53:1--53:21},
  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.53},
  URN =		{urn:nbn:de:0030-drops-264421},
  doi =		{10.4230/LIPIcs.ICALP.2026.53},
  annote =	{Keywords: Graph Algorithms, Hardness of Approximation, Polynomial Time Approximation Algorithms, Structural Graph Theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.47
A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D

Authors: Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong

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

Abstract
Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is known about the algorithmic complexity of computing it in 2D, especially when one requires either an exact solution or strong approximation guarantees. We fill this gap by introducing a 5-approximation algorithm with running time O(n⁵) under the 1-norm. This is the first constant-factor approximation for 2D CDTW with polynomial running time. We extend our algorithm to all polygonal norms on ℝ², which we subsequently use in order to achieve a (5+ε)-approximation with time complexity O(n⁵/ε^{1/2}) for CDTW in 2D under any fixed norm. The latter result in particular includes the usual Euclidean 2-norm.
Cite as

Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong. A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2026.47,
  author =	{Buchin, Kevin and Buchin, Maike and Swiadek, Jan Erik and Wong, Sampson},
  title =	{{A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{47:1--47:22},
  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.47},
  URN =		{urn:nbn:de:0030-drops-264365},
  doi =		{10.4230/LIPIcs.ICALP.2026.47},
  annote =	{Keywords: Continuous Dynamic Time Warping, Curve Similarity, Geometric Approximation Algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.51
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width

Authors: Dario Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer

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

Abstract
We prove that every class of Eulerian directed graphs of bounded carving width (equivalently, of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labelled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent, we develop a framework seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that direction. We complement our results by observing that the class of Eulerian directed graphs of unbounded degree is not well-quasi-ordered by strong immersion, even if we assume the treewidth of the class to be at most two. We conclude with a dichotomy result, proving for a very restricted class of Eulerian directed graphs of unbounded degree that it is not well-quasi-ordered by strong immersion, but it is well-quasi-ordered by weak immersion.
Cite as

Dario Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cavallaro_et_al:LIPIcs.ICALP.2026.51,
  author =	{Cavallaro, Dario and Kawarabayashi, Ken-ichi and Kreutzer, Stephan},
  title =	{{Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{51:1--51:19},
  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.51},
  URN =		{urn:nbn:de:0030-drops-264404},
  doi =		{10.4230/LIPIcs.ICALP.2026.51},
  annote =	{Keywords: algorithmic graph theory, structural graph theory, digraphs, immersions, well-quasi ordering}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.86
Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes

Authors: Anouk Duyster and Tomasz Kociumaka

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

Abstract
A Random Access query to a string T asks for the character T[i] at a given position i ∈ [0..|T|). This fundamental task admits a straightforward solution with constant-time queries and 𝒪(n log σ) bits of space when T ∈ [0..σ)ⁿ. While this is the best one can achieve in the worst case, much research has focused on the compressed setting: if T is compressible, one can hope for a much smaller data structure that still answers Random Access queries efficiently. In this work, we investigate the grammar-compressed setting, where T is represented by a context-free grammar that produces only T. Our main result is a general trade-off that optimizes Random Access time as a function of the string length n, the grammar size (the total length of productions) g, the alphabet size σ, the data structure size M, and the word size w ≥ Ω(log n) of the word RAM model. For any data structure size M satisfying glog n < Mw < nlog σ, we show an 𝒪(M)-size data structure that answers Random Access queries in time 𝒪(log((n log σ)/(Mw)) / log(Mw/(g log n))) . We also prove a matching unconditional lower bound that holds for all parameter regimes except very small grammars (g ≤ w^{1+o(1)} log n) and relatively small data structures (Mw ≤ g log n ⋅ w^o(1)). The lower bound applies to word-RAM query time and, more strongly, to the worst-case cell-probe complexity of nondeterministic or bounded-error randomized query algorithms. Previous work focused on optimizing the query time as a function of n only, achieving 𝒪(log n) time using 𝒪(g) space [Bille, Landau, Raman, Sadakane, Satti, Weimann; SIAM J. Comput. 2015] and 𝒪((log n)/(log log n)) time using 𝒪(g log^ε n) space for any constant ε > 0 [Belazzougui, Cording, Puglisi, Tabei; ESA 2015], [Ganardi, Jeż, Lohrey; J. ACM 2021]. Our result improves upon these bounds (strictly for g = n^{1-o(1)}) and generalizes them beyond M ≤ 𝒪(g poly log n), yielding a smooth interpolation with the uncompressed setting of Mw = nlogσ bits. Thus far, the only tight lower bound [Verbin and Yu; CPM 2013] was Ω((log n)/(log log n)) for w = Θ(log n), n^Ω(1) ≤ g ≤ n^{1-Ω(1), and M = g⋅log^Θ(1) n. In contrast, our result yields a tight bound that accounts for all relevant parameters and is valid for almost all parameter regimes. Our bounds remain valid for run-length grammars, where production sizes use run-length encoding. This lets us recover (and, for strings with small run-length grammars, improve) the trade-offs achieved by block trees, formulated in terms of the LZ77 size z [Belazzougui, Cáceres, Gagie, Gawrychowski, Kärkkäinen, Navarro, Ordóñez, Puglisi, Tabei; J. Comput. Syst. Sci. 2021] and substring complexity δ [Kociumaka, Navarro, Prezza; IEEE Trans. Inf. Theory 2023]. Our data structure admits an efficient deterministic construction algorithm. Beyond Random Access, its variants also support substring extraction (with optimal additive overhead 𝒪((m log σ)/w) for a length-m substring, provided that M ≥ g), as well as rank and select queries. All our results rely on novel grammar transformations that generalize contracting grammars [Ganardi; ESA 2021] and achieve the optimal trade-off between grammar size and height while enforcing extra structure crucial for constant-time navigation in the parse tree.
Cite as

Anouk Duyster and Tomasz Kociumaka. Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 86:1-86:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duyster_et_al:LIPIcs.ICALP.2026.86,
  author =	{Duyster, Anouk and Kociumaka, Tomasz},
  title =	{{Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{86:1--86:25},
  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.86},
  URN =		{urn:nbn:de:0030-drops-264755},
  doi =		{10.4230/LIPIcs.ICALP.2026.86},
  annote =	{Keywords: grammar-based compression, straight-line programs, random access problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.84
Faster and Simpler Greedy Algorithm for k-Median and k-Means

Authors: Max Dupré la Tour and David Saulpic

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

Abstract
Clustering problems such as k-means and k-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation: our algorithm matches the state-of-the-art running time for computing a constant-factor approximation in Euclidean space and graph metrics, and, in addition, is the first near-linear-time to compute a polylogarithmic approximation in Euclidean space.
Cite as

Max Dupré la Tour and David Saulpic. Faster and Simpler Greedy Algorithm for k-Median and k-Means. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duprelatour_et_al:LIPIcs.ICALP.2026.84,
  author =	{Dupr\'{e} la Tour, Max and Saulpic, David},
  title =	{{Faster and Simpler Greedy Algorithm for k-Median and k-Means}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{84:1--84:16},
  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.84},
  URN =		{urn:nbn:de:0030-drops-264735},
  doi =		{10.4230/LIPIcs.ICALP.2026.84},
  annote =	{Keywords: Clustering, k-means, approximation algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.88
Recursive Jump Operators and Optimal Proof Systems

Authors: Fabian Egidy

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

Abstract
We study the relationship between the existence of optimal proof systems and recursive jump operators, two central open problems in proof complexity. For a set L, an optimal proof system is a strongest proof system in terms of proof length, whereas a recursive jump operator uniformly transforms any proof system for L into a stronger one with respect to proof length, thereby witnessing non-optimality. It is clear that the existence of a recursive jump operator for L rules out optimal proof systems for L. Khaniki (FOCS 2024) is interested in the converse of this implication and explicitly poses the following question, where TAUT denotes the set of propositional tautologies. - Q: Does the non-existence of optimal proof systems for TAUT imply the existence of recursive jump operators for TAUT? We generalize and address this question from both a relativized and an unrelativized perspective. We show that proving a positive answer for Q is provably hard by constructing the following oracle. - O: The polynomial-time hierarchy is infinite, TAUT has no optimal proof systems, and TAUT has no recursive jump operators. This shows that Khaniki’s question can not be answered in the positive by relativizable means, even under the standard complexity-theoretic assumption that the polynomial-time hierarchy is infinite. In contrast, we obtain positive results when the question Q is posed for sets different from TAUT. We prove that the existence of recursive jump operators is upward closed under ≤_m^p-reducibility, a result that so far was only known for the non-existence of optimal proof systems. Furthermore, we show that the sets known to have no optimal proof systems by Messner (STACS 1999) in fact admit recursive jump operators. Thus, essentially all sets currently known to have no optimal proof systems have recursive jump operators.
Cite as

Fabian Egidy. Recursive Jump Operators and Optimal Proof Systems. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{egidy:LIPIcs.ICALP.2026.88,
  author =	{Egidy, Fabian},
  title =	{{Recursive Jump Operators and Optimal Proof Systems}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{88:1--88:19},
  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.88},
  URN =		{urn:nbn:de:0030-drops-264770},
  doi =		{10.4230/LIPIcs.ICALP.2026.88},
  annote =	{Keywords: Relativization, Oracles, Proof Complexity, Optimal Proof Systems, Jump Operators}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.89
Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over Greedy

Authors: Moran Feldman and Justin Ward

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

Abstract
We study the problem of maximizing a non-negative monotone submodular objective f subject to the intersection of k arbitrary matroid constraints. The natural greedy algorithm guarantees (k+1)-approximation for this problem, and the state-of-the-art algorithm only improves this approximation ratio to k. We give a (2k ln 2)/(1 + ln 2) + O(√k) < 0.819 k + O(√k) approximation algorithm for this problem. Our result is the first multiplicative improvement over the approximation ratio of the greedy algorithm for general k. We further show that our algorithm can be used to obtain roughly the same approximation ratio also for the more general problem in which the objective is not guaranteed to be monotone (the sublinear term in the approximation ratio becomes O(k^{2/3}) rather than O(√k) in this case). All of our results hold also when the k-matroid intersection constraint is replaced with a more general matroid k-parity constraint. Furthermore, unlike the case in many of the previous works, our algorithms run in time that is independent of k and polynomial in the size of the ground set. Our algorithms are based on a hybrid greedy local search approach recently introduced by Singer and Thiery [Neta Singer and Theophile Thiery, 2025] for the weighted matroid k-intersection problem, which is a special case of the problem we consider. Leveraging their approach in the submodular setting requires several non-trivial insights and algorithmic modifications since the marginals of a submodular function f, which correspond to the weights in the weighted case, are not independent of the algorithm’s internal randomness. In the special weighted case studied by [Neta Singer and Theophile Thiery, 2025], our algorithms reduce to a variant of the algorithm of [Neta Singer and Theophile Thiery, 2025] with an improved approximation ratio of (k + 1) ln 2 + O(ε) < 0.694k + 0.694 + O(ε), compared to an approximation ratio of (k+1)/(2ln 2) ≈ 0.722k + 0.722 guaranteed by Singer and Thiery [Neta Singer and Theophile Thiery, 2025].
Cite as

Moran Feldman and Justin Ward. Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over Greedy. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 89:1-89:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ICALP.2026.89,
  author =	{Feldman, Moran and Ward, Justin},
  title =	{{Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over Greedy}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{89:1--89: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.89},
  URN =		{urn:nbn:de:0030-drops-264785},
  doi =		{10.4230/LIPIcs.ICALP.2026.89},
  annote =	{Keywords: Submodular function, matroid k-parity, matroid intersection, local search, greedy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.90
New Convex Programming Technique for Nash Social Welfare and Scheduling

Authors: Yuda Feng, Weijiang Hu, and Shi Li

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

Abstract
We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching (e^{1/e} ≈ 1.445)-approximation via the rounding algorithm of Feng and Li. Unlike the exponential-size configuration LP used in prior work, our formulation can be converted into a compact linear program of polynomial size, incurring only an additive loss of ln(1+ε) in the objective. This allows the program to be solved directly using standard LP solvers, without the ellipsoid method or dual separation oracles. In the unweighted case, we show that our convex program is equivalent to the restricted-spending Fisher market convex program of Cole and Gkatzelis, yielding a constructive proof that its integrality gap is exactly e^{1/e}. With a minor modification, our analysis also gives a simple proof of the e^{1/e} EF1 gap for the identical agent setting. Finally, we show that our convex programming technique extends to two unrelated machine scheduling problems, recovering the best-known approximation ratios with simpler analyses.
Cite as

Yuda Feng, Weijiang Hu, and Shi Li. New Convex Programming Technique for Nash Social Welfare and Scheduling. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 90:1-90:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2026.90,
  author =	{Feng, Yuda and Hu, Weijiang and Li, Shi},
  title =	{{New Convex Programming Technique for Nash Social Welfare and Scheduling}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{90:1--90:22},
  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.90},
  URN =		{urn:nbn:de:0030-drops-264797},
  doi =		{10.4230/LIPIcs.ICALP.2026.90},
  annote =	{Keywords: Nash Social Welfare, Convex Programming, Approximation Algorithms, Scheduling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.91
Faster Weak Expander Decompositions and Approximate Max Flow

Authors: Henry Fleischmann, George Z. Li, and Jason Li

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

Abstract
We give faster algorithms for weak expander decompositions and approximate max flow on undirected graphs. First, we show that it is possible to "warm start" the cut-matching game when computing weak expander decompositions, avoiding the cost of the recursion depth. Our algorithm is also flexible enough to support weaker flow subroutines than previous algorithms. Our second contribution is to streamline the recent non-recursive approximate max flow algorithm of Li, Rao, and Wang (SODA, 2025) and adapt their framework to use our new weak expander decomposition primitive. Consequently, we give an approximate max flow algorithm within a few logarithmic factors of the limit of expander decomposition-based approaches.
Cite as

Henry Fleischmann, George Z. Li, and Jason Li. Faster Weak Expander Decompositions and Approximate Max Flow. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fleischmann_et_al:LIPIcs.ICALP.2026.91,
  author =	{Fleischmann, Henry and Li, George Z. and Li, Jason},
  title =	{{Faster Weak Expander Decompositions and Approximate Max Flow}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{91:1--91:20},
  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.91},
  URN =		{urn:nbn:de:0030-drops-264800},
  doi =		{10.4230/LIPIcs.ICALP.2026.91},
  annote =	{Keywords: max flow, expander decompositions, congestion approximators, cut-matching game}
}
  • Refine by Type
  • Document/HTML
  • 2982 Document/PDF

  • Refine by Publication Year
  • 892 2026
  • 1869 2025
  • 98 2024
  • 93 2023
  • 30 2022

  • Refine by Author
  • 14 Saurabh, Saket
  • 13 Rotenberg, Eva
  • 12 Fomin, Fedor V.
  • 12 Morawietz, Nils
  • 11 Chan, Timothy M.
  • Show More...

  • Refine by Series/Journal
  • 2383 LIPIcs
  • 254 OASIcs
  • 4 LITES
  • 41 TGDK
  • 300 DagRep

  • Refine by Classification
  • 243 Theory of computation → Computational geometry
  • 202 Theory of computation → Design and analysis of algorithms
  • 141 Theory of computation → Graph algorithms analysis
  • 137 Theory of computation → Distributed algorithms
  • 117 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 37 Approximation Algorithms
  • 33 machine learning
  • 33 parameterized complexity
  • 28 approximation algorithms
  • 24 Graph Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact