pith. sign in

arxiv: 2606.08217 · v1 · pith:PVSSTSNAnew · submitted 2026-06-06 · 💻 cs.DS

Revisiting Diameter in Directed Graphs

Ben Bals , Joakim Blikstad , Daniel Dadush , Yasamin Nazari , Jonas Schmidt This is my paper

Pith reviewed 2026-06-27 19:04 UTC · model grok-4.3

classification 💻 cs.DS
keywords reachability diameterfine-grained complexitydirected graphsapproximation algorithmsshortcut setshopsetstreewidthDAG width
0
0 comments X

The pith

Approximating reachability diameter in directed graphs requires cubic time under fine-grained assumptions, separating weighted and unweighted cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper initiates computational study of reachability diameter, the longest shortest path over reachable pairs in a directed graph. It establishes conditional lower bounds ruling out any approximation in weighted graphs and better than 2-approximation in unweighted graphs within O(n^{ω-ε}) time. Upper bounds include additive approximations for general unweighted graphs plus constant-factor approximations for bounded-width DAGs and bounded-treewidth graphs. These results create a weighted-unweighted separation unlike classical diameter notions and link the problem to shortcut sets and hopsets.

Core claim

Under fine-grained assumptions there is no O(n^{ω-ε}) algorithm giving any approximation of ReachDiam in weighted directed graphs, and no algorithm achieving better than 2-approximation in unweighted graphs. Additive approximation algorithms exist for unweighted graphs, while constant-factor approximations are possible for DAGs of bounded width and graphs of bounded treewidth; the same techniques yield exact hopsets with hopbound 2 on bounded-treewidth graphs.

What carries the argument

Fine-grained reductions from APSP-like problems to ReachDiam, together with dynamic-programming techniques on tree decompositions for bounded-treewidth instances.

If this is right

  • ReachDiam is computationally harder than several other directed-graph distance problems under the same assumptions.
  • Weighted and unweighted versions of the problem behave differently, unlike Min-Diameter or classical diameter.
  • Approximating ReachDiam is technically related to constructing shortcut sets and hopsets.
  • Bounded-treewidth graphs admit exact 2-hop hopsets as a byproduct.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar hardness may apply to other reachability-based aggregate measures on directed graphs.
  • Practical algorithms for ReachDiam will likely need to exploit bounded-width or low-treewidth structure or accept additive error.
  • The reduction techniques could be adapted to study diameter variants on other restricted graph families.

Load-bearing premise

The standard fine-grained hypotheses that rule out slightly sub-cubic algorithms for APSP-like problems hold.

What would settle it

An algorithm running in O(n^{ω-ε}) time that returns any constant-factor approximation of ReachDiam on weighted directed graphs, or a (2-ε)-approximation on unweighted directed graphs.

Figures

Figures reproduced from arXiv: 2606.08217 by Ben Bals, Daniel Dadush, Joakim Blikstad, Jonas Schmidt, Yasamin Nazari.

Figure 1
Figure 1. Figure 1: Our lower bound constructions for weighted ReachDiam. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Our lower bound constructions for unweighted graphs. [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

The reachability diameter ($\mathrm{ReachDiam}$) of a directed graph is the maximum distance over all pairs $u,v$ where $v$ is reachable from $u$. This notion is present in the definition of shortcut sets, and the name was recently coined in that context by Haeupler, Jiang, and Saranurak [SOSA 2026]. While this is a very natural notion of diameter in directed graphs, and especially DAGs, it is so far not computationally explored. Other definitions of diameter in directed graphs are either trivial (infinite) in graphs that are not strongly connected (e.g., the classical definition) or are non-trivial only in highly restrictive graph classes (e.g., Min-Diameter). We initiate the problem of computing the (approximate) reachability diameter from a fine-grained complexity point of view. Under certain fine-grained assumptions, we prove that there is no algorithm in time $\mathcal{O}(n^{\omega - \varepsilon}$) that gives any approximation of $\mathrm{ReachDiam}$ in weighted graphs. Similarly, there is no algorithm with better than $2$-approximation for unweighted graphs in this time. To supplement this, we provide algorithmic upper bounds that lead to additive approximation of $\mathrm{ReachDiam}$ for unweighted graphs. Hence, we establish a strong separation between the weighted and unweighted cases, which makes this type of diameter different in nature than other known notions. Considering the hardness in general weighted graphs, we also study special graph classes and get small constant approximations for DAGs with bounded width or graphs with bounded treewidth. Interestingly, our techniques also lead to exact hopsets with hopbound $2$ for bounded treewidth graphs. This and some of our upper bounds for general graphs show technical connections between approximating $\mathrm{ReachDiam}$ and computing shortcut sets and hopsets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces ReachDiam (maximum distance over reachable pairs) as a natural diameter notion for directed graphs and DAGs. From a fine-grained viewpoint, it proves conditional lower bounds showing no O(n^{ω−ε}) algorithm exists for any approximation of ReachDiam in weighted graphs, and no better than 2-approximation in unweighted graphs. Complementary upper bounds yield additive approximations for unweighted graphs in general, constant-factor approximations for bounded-width DAGs and bounded-treewidth graphs, and exact hopsets with hopbound 2 for bounded-treewidth graphs, establishing a weighted/unweighted separation and technical links to shortcut sets and hopsets.

Significance. If the results hold, the work initiates fine-grained study of ReachDiam and demonstrates a clear algorithmic separation between weighted and unweighted cases that distinguishes it from other diameter measures. The positive results on special graph classes and the hopset connections are concrete contributions that could influence research on shortcut sets and sub-cubic algorithms.

major comments (2)
  1. [Abstract / Introduction] The abstract invokes 'certain fine-grained assumptions' for the lower bounds without naming them (e.g., the precise APSP or 3SUM hypothesis); the introduction or § on hardness should state the exact hypothesis and confirm that the reduction rules out all approximations (weighted) or (2−ε)-approximations (unweighted) while preserving the time bound O(n^{ω−ε}).
  2. [Upper bounds section] The claimed separation between weighted and unweighted cases rests on the upper bounds for additive approximation in the unweighted case; the relevant section should include a precise statement of the additive error (e.g., +O(1) or +O(log n)) and the running time to allow direct comparison with the 2-approx hardness.
minor comments (2)
  1. [Abstract] The citation [SOSA 2026] for the coining of ReachDiam should be checked for accuracy (conference year or arXiv reference) and added to the bibliography.
  2. [Preliminaries] Notation for ReachDiam and related quantities (e.g., weighted vs. unweighted distances) should be introduced consistently in the preliminaries to avoid ambiguity when moving between the hardness and algorithmic sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and the helpful comments on clarity. We address each major comment below and will update the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / Introduction] The abstract invokes 'certain fine-grained assumptions' for the lower bounds without naming them (e.g., the precise APSP or 3SUM hypothesis); the introduction or § on hardness should state the exact hypothesis and confirm that the reduction rules out all approximations (weighted) or (2−ε)-approximations (unweighted) while preserving the time bound O(n^{ω−ε}).

    Authors: We agree that naming the hypotheses improves precision. In the revision we will explicitly identify the fine-grained assumptions (e.g., the APSP hypothesis) in the abstract, introduction, and hardness section, and we will add a sentence confirming that the reductions rule out every approximation factor for weighted graphs and every (2−ε)-approximation for unweighted graphs while preserving the O(n^{ω−ε}) time bound. revision: yes

  2. Referee: [Upper bounds section] The claimed separation between weighted and unweighted cases rests on the upper bounds for additive approximation in the unweighted case; the relevant section should include a precise statement of the additive error (e.g., +O(1) or +O(log n)) and the running time to allow direct comparison with the 2-approx hardness.

    Authors: We agree that an explicit statement is needed for direct comparison. We will revise the upper-bounds section to state the precise additive error term and the running time of the algorithm, allowing immediate juxtaposition with the 2-approximation hardness result. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes conditional lower bounds for approximating ReachDiam under external fine-grained hypotheses (standard APSP-style assumptions ruling out O(n^{ω-ε}) time) and supplies matching algorithmic upper bounds for additive approximations and special graph classes. These hypotheses are invoked as given external inputs rather than derived internally; the name ReachDiam is attributed to an independent prior citation (Haeupler et al., SOSA 2026) with no author overlap. No self-definitional equations, fitted inputs renamed as predictions, load-bearing self-citations, or ansatz smuggling appear. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on unspecified fine-grained complexity assumptions and standard graph-theoretic definitions; no free parameters, invented entities, or additional axioms are visible in the abstract.

axioms (1)
  • domain assumption Certain fine-grained complexity assumptions (e.g., no slightly sub-cubic APSP algorithm) hold.
    Invoked in the abstract to obtain the conditional lower bounds on approximation algorithms.

pith-pipeline@v0.9.1-grok · 5883 in / 1285 out tokens · 16816 ms · 2026-06-27T19:04:28.845047+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Structural parameterizations of Geodetic Set on directed (acyclic) graphs

    cs.DS 2026-06 unverdicted novelty 6.0

    Directed Geodetic Set admits a 2^{O(vcn)} kernel on digraphs and a (kΔ)^{O(rdiam)} kernel, with ETH-tight runtimes, and remains W[2]-hard parameterized by k on degree-3 DAGs.

Reference graph

Works this paper leans on

43 extracted references · 35 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [2]

    New graph decompositions and combinatorial boolean matrix multiplication algorithms

    Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka. New graph decompositions and combinatorial boolean matrix multiplication algorithms. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 935–943, New York, NY, USA, 2024. Association for Computing Machinery.doi:10.1145/3618260.3649696

    work page doi:10.1145/3618260.3649696 2024

  2. [3]

    Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

    Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. InProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 377–391. Society for Industrial and Applied Mathematics, January 2016. URL:http://epubs.siam.org/doi/10....

    work page doi:10.1137/1.9781611974331.ch28 2016

  3. [4]

    More asymmetry yields faster matrix multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. InProceedings of the 2025 Annual ACM-SIAM Sym- posium on Discrete Algorithms (SODA), pages 2005–2039, 2025. URL:https://epubs.siam.org/ doi/abs/10.1137/1.9781611978322.63,arXiv:https://epubs.siam.org/doi/pdf/10.1...

    work page doi:10.1137/1.9781611978322.63 2025

  4. [5]

    Covering approximate shortest paths with dags

    Sepehr Assadi, Gary Hoppenworth, and Nicole Wein. Covering approximate shortest paths with dags. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 2269–2280, New York, NY, USA, 2025. Association for Computing Machinery.doi:10.1145/3717823.3718298

    work page doi:10.1145/3717823.3718298 2025

  5. [6]

    Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Toward tight approximation bounds for graph diameter and eccentricities.SIAM Journal on Computing, 50(4):1155–1199, 2021.arXiv:https://doi.org/10.1137/18M1226737,doi:10.1137/18M1226737

    work page doi:10.1137/18m1226737 2021

  6. [7]

    New techniques and fine-grained hardness for dynamic near-additive spanners

    Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New techniques and fine-grained hardness for dynamic near-additive spanners. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1836–1855. SIAM, 2021

    2021

  7. [8]

    Approximating min-diameter: Standard and bichromatic

    Aaron Berger, Jenny Kaufmann, and Virginia Vassilevska Williams. Approximating min-diameter: Standard and bichromatic. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, September 4-6, 2023, volume 274 ofLIPIcs, pages 17:1–17:14. Schlos...

    work page doi:10.4230/lipics.esa.2023.17 2023

  8. [9]

    2022 , volume =

    Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), page 1000–1008. IEEE, February 2022. URL:http://dx.doi.org/10. 1109/FOCS52979.2021.00100,doi:10.1109/focs52979.2021.00100

    work page doi:10.1109/focs52979.2021.00100 2022

  9. [10]

    Woodruff

    Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners.SIAM J. Comput., 41(6):1380–1425, 2012.doi:10.1137/110826655

    work page doi:10.1137/110826655 2012

  10. [11]

    On small-depth Frege proofs for

    Greg Bodwin and Gary Hoppenworth. Folklore sampling is optimal for exact hopsets: Confirming the √n barrier. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 701–720. IEEE, 2023.doi:10.1109/FOCS57990.2023.00046

    work page doi:10.1109/focs57990.2023.00046 2023

  11. [12]

    4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time𝑛 4/3

    ´Edouard Bonnet. 4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time𝑛 4/3. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, Lan- guages, and Programming (ICALP 2021), volume 198 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:15, Dagstuhl, Germany, 2021. Schl...

    work page doi:10.4230/lipics.icalp.2021.34 2021

  12. [13]

    Approximating apsp without scaling: equivalence of approximate min-plus and exact min-max

    Karl Bringmann, Marvin K¨ unnemann, and Karol Wegrzycki. Approximating apsp without scaling: equivalence of approximate min-plus and exact min-max. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC ’19, page 943–954. ACM, June 2019. URL: http://dx.doi.org/10.1145/3313276.3316373,doi:10.1145/3313276.3316373

    work page doi:10.1145/3313276.3316373 2019

  13. [14]

    Minimum Chain Cover in Almost Linear Time, May 2023

    Manuel Caceres. Minimum Chain Cover in Almost Linear Time, May 2023. arXiv:2305.02166 [cs]. URL: http://arxiv.org/abs/2305.02166,doi:10.48550/arXiv.2305.02166

    work page doi:10.48550/arxiv.2305.02166 2023

  14. [15]

    Shortcuts and transitive-closure spanners approximation.CoRR, abs/2502.08032, 2025

    Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, and Danupon Nanongkai. Shortcuts and transitive-closure spanners approximation.CoRR, abs/2502.08032, 2025. To appear in SODA

    arXiv 2025

  15. [16]

    URL:https://doi.org/10.48550/arXiv.2502.08032,arXiv:2502.08032,doi:10.48550/ ARXIV.2502.08032

    work page doi:10.48550/arxiv.2502.08032

  16. [17]

    Stephan, Y

    Shiri Chechik and Tianyi Zhang. Constant approximation of min-distances in near-linear time. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 896–906. IEEE, 2022.doi:10.1109/FOCS54457.2022.00089

    work page doi:10.1109/focs54457.2022.00089 2022

  17. [18]

    Springer, 2015

    Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume 5. Springer, 2015

    2015

  18. [19]

    Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles, September 2022

    Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, and Nicole Wein. Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles, September 2022. arXiv:2204.03076 [cs]. URL:http://arxiv.org/abs/2204.03076,doi:10.48550/arXiv.2204.03076

    work page doi:10.48550/arxiv.2204.03076 2022

  19. [20]

    Approximation Algorithms for Min-Distance Problems in DAGs, October 2022.arXiv:2106.02120,doi:10.48550/arXiv.2106.02120

    Mina Dalirrooyfard and Jenny Kaufmann. Approximation Algorithms for Min-Distance Problems in DAGs, October 2022.arXiv:2106.02120,doi:10.48550/arXiv.2106.02120

    work page doi:10.48550/arxiv.2106.02120 2022

  20. [21]

    Sparse matrix multiplication and triangle listing in the congested clique model

    Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation algorithms for min-distance problems. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors,46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, July 9-1...

    work page doi:10.4230/lipics 2019

  21. [22]

    Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs

    Sally Dong and Guanghao Ye. Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs. In Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:14, Dagstuhl, Germany, 2...

    work page doi:10.4230/lipics.esa.2024 2024

  22. [23]

    The diameter of at-free graphs.Journal of Graph Theory, 99(4):594–614, 2022

    Guillaume Ducoffe. The diameter of at-free graphs.Journal of Graph Theory, 99(4):594–614, 2022

    2022

  23. [24]

    Eccentricity queries and beyond using hub labels.Theoretical Computer Science, 930:128–141, 2022

    Guillaume Ducoffe. Eccentricity queries and beyond using hub labels.Theoretical Computer Science, 930:128–141, 2022. URL:https://www.sciencedirect.com/science/article/pii/ S0304397522004443,doi:10.1016/j.tcs.2022.07.017

    work page doi:10.1016/j.tcs.2022.07.017 2022

  24. [25]

    Stochastic embedding of digraphs into dags.CoRR, abs/2509.23458, 2025

    Arnold Filtser. Stochastic embedding of digraphs into dags.CoRR, abs/2509.23458, 2025. To appear in SODA 2026. URL:https://doi.org/10.48550/arXiv.2509.23458,arXiv:2509.23458,doi: 10.48550/ARXIV.2509.23458

    work page doi:10.48550/arxiv.2509.23458 2025

  25. [26]

    Jeremy T. Fineman. Nearly Work-Efficient Parallel Algorithm for Digraph Reachability, November 2017. arXiv:1711.01700 [cs]. URL:http://arxiv.org/abs/1711.01700,doi:10.48550/arXiv.1711. 01700

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1711 2017

  26. [27]

    Distance labeling in graphs.Journal of algorithms, 53(1):85–112, 2004

    Cyril Gavoille, David Peleg, St ´ephane P ´erennes, and Ran Raz. Distance labeling in graphs.Journal of algorithms, 53(1):85–112, 2004

    2004

  27. [28]

    Reducing shortcut and hopset constructions to shallow graphs.CoRR, abs/2508.20302, 2025

    Bernhard Haeupler, Yonggang Jiang, and Thatchaphol Saranurak. Reducing shortcut and hopset constructions to shallow graphs.CoRR, abs/2508.20302, 2025. To appear in SOSA 2026. URL:https://doi.org/10. 48550/arXiv.2508.20302,arXiv:2508.20302,doi:10.48550/ARXIV.2508.20302. 18

    work page doi:10.48550/arxiv.2508.20302 2025

  28. [29]

    C. S. Karthik and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic.Combinatorica, 40(4):539–573, April 2020. URL:http://dx.doi.org/10.1007/ s00493-019-4113-1,doi:10.1007/s00493-019-4113-1

    work page doi:10.1007/s00493-019-4113-1 2020

  29. [30]

    Finding and counting small induced subgraphs efficiently.In- formation Processing Letters, 74(3):115–121, 2000

    Ton Kloks, Dieter Kratsch, and Haiko M¨ uller. Finding and counting small induced subgraphs efficiently.In- formation Processing Letters, 74(3):115–121, 2000. URL:https://www.sciencedirect.com/science/ article/pii/S0020019000000478,doi:10.1016/S0020-0190(00)00047-8

    work page doi:10.1016/s0020-0190(00)00047-8 2000

  30. [31]

    Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers

    Shimon Kogan and Merav Parter. Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers. In Nikhil Bansal and Viswanath Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 212–239. SIAM, 2023. URL:https://doi.org/10.1137/1.9781611977554...

    work page doi:10.1137/1.9781611977554.ch9 2023

  31. [32]

    The algorithmic power of the greene-kleitman theorem

    Shimon Kogan and Merav Parter. The algorithmic power of the greene-kleitman theorem. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, volume 308 ofLIPIcs, pages 80:1–80:14. Schloss Dagstuhl - Leibniz-Zentrum f...

    work page doi:10.4230/lipics.esa.2024.80 2024

  32. [33]

    Giving some slack: Shortcuts and transitive closure compressions

    Shimon Kogan and Merav Parter. Giving some slack: Shortcuts and transitive closure compressions. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, volume 308 ofLIPIcs, pages 79:1–79:15. Schloss Dagstuhl - Leibn...

    work page doi:10.4230/lipics.esa.2024.79 2024

  33. [34]

    Between o(nm) and o(na)

    Dieter Kratsch and Jeremy Spinrad. Between o(nm) and o(na). InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, page 709–716, USA, 2003. Society for Industrial and Applied Mathematics

    2003

  34. [35]

    Settling seth vs

    Ray Li. Settling seth vs. approximate sparse directed unweighted diameter (up to (nu)nseth). InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 1684–1696, New York, NY, USA, 2021. Association for Computing Machinery.doi:10.1145/3406325.3451045

    work page doi:10.1145/3406325.3451045 2021

  35. [36]

    HiGitClass: Keyword-driven hierarchical classi- fication of GitHub repositories,

    Yang P. Liu, Arun Jambulapati, and Aaron Sidford. Parallel reachability in almost linear work and square root depth. In David Zuckerman, editor,60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1664–1686. IEEE Computer Society, 2019.doi:10.1109/FOCS.2019.00098

    work page doi:10.1109/focs.2019.00098 2019

  36. [37]

    Dag-width: connectivity measure for directed graphs

    Jan Obdrz ´alek. Dag-width: connectivity measure for directed graphs. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22- 26, 2006, pages 814–821. ACM Press, 2006. URL:http://dl.acm.org/citation.cfm?id=1109557. 1109647

    2006

  37. [38]

    Fast approximation algorithms for the diameter and radius of sparse graphs

    Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. InProceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 515– 524, Palo Alto California USA, June 2013. ACM. URL:https://dl.acm.org/doi/10.1145/2488608. 2488673,doi:10.1145/2488608.2488673

    work page doi:10.1145/2488608 2013

  38. [39]

    Fast approximation algorithms for the diameter and radius of sparse graphs

    Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. InProceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 515–524, New York, NY, USA, 2013. Association for Computing Machinery.doi: 10.1145/2488608.2488673

    work page doi:10.1145/2488608.2488673 2013

  39. [40]

    Hardness of approximate nearest neighbor search

    Aviad Rubinstein. Hardness of approximate nearest neighbor search. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1260–1268, New York, NY, USA, 2018. Association for Computing Machinery.doi:10.1145/3188745.3188916

    work page doi:10.1145/3188745.3188916 2018

  40. [41]

    Ryan Williams

    Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5):27:1–27:38, 2018.doi:10.1145/3186893

    work page doi:10.1145/3186893 2018

  41. [42]

    A new algorithm for optimal 2-constraint satisfaction and its implications.Theoreti- cal Computer Science, 348(2):357–365, 2005

    Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications.Theoreti- cal Computer Science, 348(2):357–365, 2005. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004). URL:https://www.sciencedirect.com/science/article/pii/ S0304397505005438,doi:10.1016/j.tcs.2005.09.023. 19

    work page doi:10.1016/j.tcs.2005.09.023 2005

  42. [43]

    On some fine-grained questions in algorithms and complexity.Proceedings of the International Congress of Mathematicians (ICM 2018), 2019

    Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity.Proceedings of the International Congress of Mathematicians (ICM 2018), 2019. URL:https://api.semanticscholar. org/CorpusID:19282287

    2018

  43. [44]

    All pairs shortest paths using bridging sets and rectangular matrix multiplication.Journal of the ACM, 49(3):289–317, May 2002

    Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication.Journal of the ACM, 49(3):289–317, May 2002. URL:http://dx.doi.org/10.1145/567112.567114,doi: 10.1145/567112.567114. 20

    work page doi:10.1145/567112.567114 2002