20 Search Results for "Akmal, Shyan"

Document
DOI: 10.4230/LIPIcs.STACS.2026.36
Time-Optimal Construction of String Synchronizing Sets

Authors: Jonas Ellert and Tomasz Kociumaka

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
A powerful design principle behind many modern string algorithms is local consistency: breaking the symmetry between string positions based on their small contexts so that matching fragments are handled consistently. Among the most influential instantiations of this principle are string synchronizing sets [Kempa & Kociumaka; STOC 2019]. A τ-synchronizing set of a string of length n is a set of O(n/τ) string positions, chosen using their length-2τ contexts, such that (outside of highly periodic regions) every block of τ consecutive positions contains at least one element of the set. Synchronizing sets have found dozens of applications in diverse settings, from quantum and dynamic algorithms to fully compressed computation. In the classic word RAM model, particularly for strings over small alphabets, they enabled faster solutions to core problems in data compression, text indexing, and string similarity. In this work, we show that any string T ∈ [0 .. σ)ⁿ can be preprocessed in O(n log σ / log n) time so that, for any given integer τ ∈ [1 .. n], a τ-synchronizing set of T can be constructed in O((n log τ)/(τ log n)) time. Both bounds are optimal in the word RAM model with machine word size w = Θ(log n), matching the information-theoretic minimum for the input and output sizes, respectively. Previously, constructing a τ-synchronizing set required O(n/τ) time after an O(n)-time preprocessing [Kociumaka, Radoszewski, Rytter, and Waleń; SICOMP 2024], or, in the restricted regime of τ < 0.2 log_σ n, without any preprocessing needed [Kempa & Kociumaka; STOC 2019]. A simple instantiation of our method outputs the synchronizing set as a sorted list in O(n/τ) time, or as a bitmask in O(n/log n) time. Our optimal construction produces a compact fully indexable dictionary, supporting select queries in O(1) time and rank queries in O(log ((log τ)/(log log n))) time. The latter complexity matches known unconditional cell-probe lower bounds for τ ≤ n^{1-Ω(1)}. To achieve this, we introduce a general framework for efficiently processing sparse integer sequences via a custom variable-length encoding. We also augment the optimal variant of van Emde Boas trees [Pătraşcu & Thorup; STOC 2006] with a deterministic linear-time construction. When the set is represented as a bitmask under our sparse encoding, the same guarantees for select and rank queries hold after preprocessing in time proportional to the size of our encoding (in words).
Cite as

Jonas Ellert and Tomasz Kociumaka. Time-Optimal Construction of String Synchronizing Sets. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ellert_et_al:LIPIcs.STACS.2026.36,
  author =	{Ellert, Jonas and Kociumaka, Tomasz},
  title =	{{Time-Optimal Construction of String Synchronizing Sets}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.36},
  URN =		{urn:nbn:de:0030-drops-255258},
  doi =		{10.4230/LIPIcs.STACS.2026.36},
  annote =	{Keywords: synchronizing sets, local consistency, packed strings}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.39
Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions

Authors: Keerti Choudhary, Amit Kumar, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs (s₁,t₁) and (s₂,t₂), decide whether there exist vertex-disjoint shortest paths between each pair. Building on recent advances in disjoint shortest paths for DAGs and undirected graphs (Akmal et al. 2024), we present an O(mn log n)-time algorithm for this problem in weighted directed graphs that do not contain negative or zero weight cycles. This algorithm presents a significant improvement over the previously known O(m⁵n)-time bound (Berczi et al. 2017). Our approach exploits the algebraic structure of polynomials that enumerate shortest paths between terminal pairs. A key insight is that these polynomials admit a recursive decomposition, enabling efficient evaluation via dynamic programming over fields of characteristic two. Furthermore, we demonstrate how to report the corresponding paths in O(mn² log n)-time. In addition, we extend our techniques to a more general setting: given two terminal pairs (s₁, t₁) and (s₂, t₂) in a directed graph, find the minimum possible number of vertex intersections between any shortest path from s₁ to t₁ and s₂ to t₂. We call this the Minimum 2-Disjoint Shortest Paths (Min-2-DSP) problem. We provide in this paper the first efficient algorithm for this problem, including an O(m² n³)-time algorithm for directed graphs with positive edge weights, and an O(m+n)-time algorithm for DAGs and undirected graphs. Moreover, if the number of intersecting vertices is at least one, we show that it is possible to report the paths in the same O(m+n)-time. This is somewhat surprising, as there is no known o(mn) time algorithm for explicitly reporting the paths if they are vertex-disjoint, and is left as an open problem in (Akmal et al. 2024).
Cite as

Keerti Choudhary, Amit Kumar, and Lakshay Saggi. Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.ITCS.2026.39,
  author =	{Choudhary, Keerti and Kumar, Amit and Saggi, Lakshay},
  title =	{{Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.39},
  URN =		{urn:nbn:de:0030-drops-253267},
  doi =		{10.4230/LIPIcs.ITCS.2026.39},
  annote =	{Keywords: Disjoint paths, Disjoint shortest paths, Algebraic graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.5
Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs

Authors: Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
This paper addresses the problem of designing fault-tolerant data structures for the (s,t)-max-flow and (s,t)-min-cut problems in unweighted directed graphs. Given a directed graph G = (V, E) with a designated source s, sink t, and an (s,t)-max-flow of value λ, we present constructions for max-flow and min-cut sensitivity oracles, and introduce the concept of a fault-tolerant flow family, which may be of independent interest. Our main contributions are as follows. 1) Fault-Tolerant Flow Family: We construct a family ℬ of 2λ+1 (s,t)-flows such that for every edge e, ℬ contains an (s,t)-max-flow of G-e. This covering property is tight up to constants for single failures and provably cannot extend to comparably small families for k ≥ 2, where we show an Ω(n) lower bound on the family size, independent of λ. 2) Max-Flow Sensitivity Oracle: Using the fault-tolerant flow family, we construct a single as well as dual-edge sensitivity oracle for (s,t)-max-flow that requires only O(λ n) space. Given any set F of up to two failing edges, the oracle reports the updated max-flow value in G-F in O(n) time. Additionally, for the single-failure case, the oracle can determine in constant time whether the flow through an edge x changes when another edge e fails. 3) Min-Cut Sensitivity Oracle for Dual Failures: Recently, Baswana et al. (ICALP’22) designed an O(n²)-sized oracle for answering (s,t)-min-cut size queries under dual edge failures in constant time, along with a matching lower bound. We extend this by focusing on graphs with small min-cut values λ, and present a more compact oracle of size O(λ n) that answers such min-cut size queries in constant time and reports the corresponding (s,t)-min-cut partition in O(n) time. We also show that the space complexity of our oracle is asymptotically optimal in this setting. 4) Min-Cut Sensitivity Oracle for Multiple Failures: We extend our results to the general case of k edge failures. For any graph with (s,t)-min-cut of size λ, we construct a k-fault-tolerant min-cut oracle with space complexity O_{λ,k}(n log n) that answers min-cut size queries in O_{λ,k}(log n) time. This also leads to improved fault-tolerant (s,t)-reachability oracles, achieving O(n log n) space and O(log n) query time for up to k = O(1) edge failures.
Cite as

Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi. Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahi_et_al:LIPIcs.ITCS.2026.5,
  author =	{Ahi, Mridul and Choudhary, Keerti and Pande, Shlok and Pushpraj and Saggi, Lakshay},
  title =	{{Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.5},
  URN =		{urn:nbn:de:0030-drops-252920},
  doi =		{10.4230/LIPIcs.ITCS.2026.5},
  annote =	{Keywords: Fault tolerance, Data structures, Minimum cuts, Maximum flows}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.5
Graph Coloring Below Guarantees via Co-Triangle Packing

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In the 𝓁-Coloring problem, we are given a graph on n nodes, and tasked with determining if its vertices can be properly colored using 𝓁 colors. In this paper we study below-guarantee graph coloring, which tests whether an n-vertex graph can be properly colored using g-k colors, where g is a trivial upper bound such as n. We introduce an algorithmic framework that builds on a packing of co-triangles K₃ (independent sets of three vertices): the algorithm greedily finds co-triangles and employs a win-win analysis. If many are found, we immediately return yes; otherwise these co-triangles form a small co-triangle modulator, whose deletion makes the graph co-triangle-free. Extending the work of [Gutin et al., SIDMA 2021], who solved 𝓁-Coloring (for any 𝓁) in randomized O^∗(2^k) time when given a K₂-free modulator of size k, we show that this problem can likewise be solved in randomized O^*(2^{k}) time when given a K₃-free modulator of size k. This result in turn yields a randomized O^*(2^{3k/2}) algorithm for (n-k)-Coloring (also known as Dual Coloring), improving the previous O^*(4^k) bound. We then introduce a smaller parameterization, (ω+μ-k)-Coloring, where ω is the clique number and μ is the size of a maximum matching in the complement graph; since ω+μ ≤ n for any graph, this problem is strictly harder. Using the same co-triangle-packing argument, we obtain a randomized O^*(2^{6k}) algorithm, establishing its fixed-parameter tractability for a smaller parameter. Complementing this finding, we show that no fixed-parameter tractable algorithm exists for (ω-k)-Coloring or (μ-k)-Coloring under standard complexity assumptions.
Cite as

Shyan Akmal and Tomohiro Koana. Graph Coloring Below Guarantees via Co-Triangle Packing. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ISAAC.2025.5,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Graph Coloring Below Guarantees via Co-Triangle Packing}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.5},
  URN =		{urn:nbn:de:0030-drops-249130},
  doi =		{10.4230/LIPIcs.ISAAC.2025.5},
  annote =	{Keywords: coloring, parameterized algorithms, algebraic algorithms, above-guarantee, below-guarantee, subset convolution, determinants}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.51
Quantum Approximate k-Minimum Finding

Authors: Minbo Gao, Zhengfeng Ji, and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum k-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum k-minimum finding algorithm that works with approximate values for all k ≥ 1, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for k = 1. As practical applications, we present efficient quantum algorithms for identifying the k smallest expectation values among multiple observables and for determining the k lowest ground state energies of a Hamiltonian with a known eigenbasis.
Cite as

Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum Approximate k-Minimum Finding. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ESA.2025.51,
  author =	{Gao, Minbo and Ji, Zhengfeng and Wang, Qisheng},
  title =	{{Quantum Approximate k-Minimum Finding}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.51},
  URN =		{urn:nbn:de:0030-drops-245192},
  doi =		{10.4230/LIPIcs.ESA.2025.51},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Quantum Minimum Finding}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.94
Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime

Authors: Tomasz Kociumaka and Ali Shahali

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The tree edit distance is a natural dissimilarity measure between rooted ordered trees whose nodes are labeled over an alphabet Σ. It is defined as the minimum number of node edits - insertions, deletions, and relabelings - required to transform one tree into the other. The weighted variant assigns costs ≥ 1 to edits (based on node labels), minimizing total cost rather than edit count. The unweighted tree edit distance between two trees of total size n can be computed in 𝒪(n^{2.6857}) time; in contrast, determining the weighted tree edit distance is fine-grained equivalent to the All-Pairs Shortest Paths (APSP) problem and requires n³/2^Ω(√{log n}) time [Nogler, Polak, Saha, Vassilevska Williams, Xu, Ye; STOC'25]. These impractical super-quadratic times for large, similar trees motivate the bounded version, parameterizing runtime by the distance k to enable faster algorithms for k ≪ n. Prior algorithms for bounded unweighted edit distance achieve 𝒪(nk²log n) [Akmal & Jin; ICALP’21] and 𝒪(n + k⁷log k) [Das, Gilbert, Hajiaghayi, Kociumaka, Saha; STOC'23]. For weighted, only 𝒪(n + k^{15}) is known [Das, Gilbert, Hajiaghayi, Kociumaka, Saha; STOC'23]. We present an 𝒪(n + k⁶ log k)-time algorithm for bounded tree edit distance in both weighted/unweighted settings. First, we devise a simpler weighted 𝒪(nk² log n)-time algorithm. Next, we exploit periodic structures in input trees via an optimized universal kernel: modifying prior 𝒪(n)-time 𝒪(k⁵)-size kernels to generate such structured instances, enabling efficient analysis.
Cite as

Tomasz Kociumaka and Ali Shahali. Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 94:1-94:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kociumaka_et_al:LIPIcs.ESA.2025.94,
  author =	{Kociumaka, Tomasz and Shahali, Ali},
  title =	{{Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{94:1--94:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.94},
  URN =		{urn:nbn:de:0030-drops-245634},
  doi =		{10.4230/LIPIcs.ESA.2025.94},
  annote =	{Keywords: tree edit distance, edit distance, kernelization, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.86
New Algorithms for Pigeonhole Equal Subset Sum

Authors: Ce Jin, Ryan Williams, and Stan Zhang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the Pigeonhole Equal Subset Sum problem, which is a total-search variant of the Subset Sum problem introduced by Papadimitriou (1994): we are given a set of n positive integers {w₁,…,w_n} with the additional restriction that ∑_{i=1}^n w_i < 2ⁿ - 1, and want to find two different subsets A,B ⊆ [n] such that ∑_{i∈A} w_i = ∑_{i∈B} w_i. Very recently, Jin and Wu (ICALP 2024) gave a randomized algorithm solving Pigeonhole Equal Subset Sum in O^*(2^{0.4n}) time, beating the classical meet-in-the-middle algorithm with O^*(2^{n/2}) runtime. In this paper, we refine Jin and Wu’s techniques to improve the runtime even further to O^*(2^{n/3}).
Cite as

Ce Jin, Ryan Williams, and Stan Zhang. New Algorithms for Pigeonhole Equal Subset Sum. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 86:1-86:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ESA.2025.86,
  author =	{Jin, Ce and Williams, Ryan and Zhang, Stan},
  title =	{{New Algorithms for Pigeonhole Equal Subset Sum}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{86:1--86:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.86},
  URN =		{urn:nbn:de:0030-drops-245541},
  doi =		{10.4230/LIPIcs.ESA.2025.86},
  annote =	{Keywords: pigeonhole principle, subset sums}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.6
QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More

Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Despite the wide range of problems for which quantum computers offer a computational advantage over their classical counterparts, there are also many problems for which the best known quantum algorithm provides a speedup that is only quadratic, or even subquadratic. Such a situation could also be desirable if we don't want quantum computers to solve certain problems fast - say problems relevant to post-quantum cryptography. When searching for algorithms and when analyzing the security of cryptographic schemes, we would like to have evidence that these problems are difficult to solve on quantum computers; but how do we assess the exact complexity of these problems? For most problems, there are no known ways to directly prove time lower bounds, however it can still be possible to relate the hardness of disparate problems to show conditional lower bounds. This approach has been popular in the classical community, and is being actively developed for the quantum case [Aaronson et al., 2020; Buhrman et al., 2021; Harry Buhrman et al., 2022; Andris Ambainis et al., 2022]. In this paper, by the use of the QSETH framework [Buhrman et al., 2021] we are able to understand the quantum complexity of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT, and also are able to comment on the non-trivial complexity of approximate versions of counting-CNFSAT. Without considering such variants, the best quantum lower bounds will always be quadratically lower than the equivalent classical bounds, because of Grover’s algorithm; however, we are able to show that quantum algorithms will likely not attain even a quadratic speedup for many problems. These results have implications for the complexity of (variations of) lattice problems, the strong simulation and hitting set problems, and more. In the process, we explore the QSETH framework in greater detail and present a useful guide on how to effectively use the QSETH framework.
Cite as

Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, and Florian Speelman. QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.6,
  author =	{Chen, Yanlin and Chen, Yilei and Kumar, Rajendra and Patro, Subhasree and Speelman, Florian},
  title =	{{QSETH Strikes Again: Finer Quantum Lower Bounds for Lattice Problem, Strong Simulation, Hitting Set Problem, and More}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.6},
  URN =		{urn:nbn:de:0030-drops-243723},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.6},
  annote =	{Keywords: Quantum conditional lower bounds, Fine-grained complexity, Lattice problems, Quantum strong simulation, Hitting set problem, QSETH}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.9
On the Quantum Time Complexity of Divide and Conquer

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
Cite as

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha. On the Quantum Time Complexity of Divide and Conquer. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{allcock_et_al:LIPIcs.ICALP.2025.9,
  author =	{Allcock, Jonathan and Bao, Jinge and Belovs, Aleksandrs and Lee, Troy and Santha, Miklos},
  title =	{{On the Quantum Time Complexity of Divide and Conquer}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.9},
  URN =		{urn:nbn:de:0030-drops-233863},
  doi =		{10.4230/LIPIcs.ICALP.2025.9},
  annote =	{Keywords: Quantum Computing, Quantum Algorithms, Divide and Conquer}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.51
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

Authors: Shion Fukuzawa, Michael T. Goodrich, and Sandy Irani

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output.
Cite as

Shion Fukuzawa, Michael T. Goodrich, and Sandy Irani. Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fukuzawa_et_al:LIPIcs.SoCG.2025.51,
  author =	{Fukuzawa, Shion and Goodrich, Michael T. and Irani, Sandy},
  title =	{{Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.51},
  URN =		{urn:nbn:de:0030-drops-232035},
  doi =		{10.4230/LIPIcs.SoCG.2025.51},
  annote =	{Keywords: quantum computing, computational geometry, divide and conquer, convex hulls, maxima sets}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.17
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Authors: Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) n-vertex graph G along with k terminal pairs (s_1,t_1),(s_2,t_2),…,(s_k,t_k). The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA '21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k. Lochet’s result implies the existence of a polynomial-time ck-approximation for Maximum Vertex-Disjoint Shortest Paths, where c ≤ 1 is a constant. (One can guess 1/c terminal pairs to connect in k^O(1/c) time and then utilize Lochet’s algorithm to compute the solution in n^f(1/c) time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o(k)-approximation within f(k) ⋅ poly(n) time for any function f that only depends on k. Our second result demonstrates the infeasibility of achieving an approximation ratio of m^{1/2-ε} in polynomial time, unless P = NP. It is not difficult to show that a greedy algorithm selecting a path with the minimum number of arcs results in a ⌈√𝓁⌉-approximation, where 𝓁 is the number of edges in all the paths of an optimal solution. Since 𝓁 ≤ n, this underscores the tightness of the m^{1/2-ε}-inapproximability bound. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when parameterized by 𝓁 but does not admit a polynomial kernel. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.
Cite as

Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach. Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2025.17,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A.},
  title =	{{Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.17},
  URN =		{urn:nbn:de:0030-drops-228422},
  doi =		{10.4230/LIPIcs.STACS.2025.17},
  annote =	{Keywords: Inapproximability, Fixed-parameter tractability, Parameterized approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.7
Faster Edge Coloring by Partition Sieving

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In the Edge Coloring problem, we are given an undirected graph G with n vertices and m edges, and are tasked with finding the smallest positive integer k so that the edges of G can be assigned k colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in 2^mpoly(n) time and polynomial space, and in graphs with average degree d in 2^{(1-ε_d)m}⋅poly(n) time and exponential space, where ε_d = (1/d)^Θ(d³). We present an algorithm that solves Edge Coloring in 2^{m-3n/5}⋅poly(n) time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than 2^m⋅poly(m) time and uses only polynomial space. In graphs of average degree d, our algorithm runs in 2^{(1-6/(5d))m}⋅poly(n) time, which has far better dependence in d than previous results. We also consider a generalization of Edge Coloring called List Edge Coloring, where each edge e in the input graph comes with a list L_e ⊆ {1, …, k} of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We show that this problem can be solved in 2^{(1-6/(5k))m}⋅poly(n) time and polynomial space. The previous best algorithm for List Edge Coloring took 2^m⋅poly(n) time and space. Our algorithms are algebraic, and work by constructing a special polynomial P based off the input graph that contains a multilinear monomial (i.e., a monomial where every variable has degree at most one) if and only if the answer to the List Edge Coloring problem on the input graph is YES. We then solve the problem by detecting multilinear monomials in P. Previous work also employed such monomial detection techniques to solve Edge Coloring. We obtain faster algorithms both by carefully constructing our polynomial P, and by improving the runtimes for certain structured monomial detection problems using a technique we call partition sieving.
Cite as

Shyan Akmal and Tomohiro Koana. Faster Edge Coloring by Partition Sieving. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.STACS.2025.7,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Faster Edge Coloring by Partition Sieving}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.7},
  URN =		{urn:nbn:de:0030-drops-228328},
  doi =		{10.4230/LIPIcs.STACS.2025.7},
  annote =	{Keywords: Coloring, Edge coloring, Chromatic index, Matroid, Pfaffian, Algebraic algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.9
Detecting Disjoint Shortest Paths in Linear Time and More

Authors: Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein

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

Abstract
In the k-Disjoint Shortest Paths (k-DSP) problem, we are given a graph G (with positive edge weights) on n nodes and m edges with specified source vertices s_1, … , s_k, and target vertices t_1, … , t_k, and are tasked with determining if G contains vertex-disjoint (s_i,t_i)-shortest paths. For any constant k, it is known that k-DSP can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs). However, the exact time complexity of k-DSP remains mysterious, with large gaps between the fastest known algorithms and best conditional lower bounds. In this paper, we obtain faster algorithms for important cases of k-DSP, and present better conditional lower bounds for k-DSP and its variants. Previous work solved 2-DSP over weighted undirected graphs in O(n⁷) time, and weighted DAGs in O(mn) time. For the main result of this paper, we present optimal linear time algorithms for solving 2-DSP on weighted undirected graphs and DAGs. Our linear time algorithms are algebraic however, and so only solve the detection rather than search version of 2-DSP (we show how to solve the search version in O(mn) time, which is faster than the previous best runtime in weighted undirected graphs, but only matches the previous best runtime for DAGs). We also obtain a faster algorithm for k-Edge Disjoint Shortest Paths (k-EDSP) in DAGs, the variant of k-DSP where one seeks edge-disjoint instead of vertex-disjoint paths between sources and their corresponding targets. Algorithms for k-EDSP on DAGs from previous work take Ω(m^k) time. We show that k-EDSP can be solved over DAGs in O(mn^{k-1}) time, matching the fastest known runtime for solving k-DSP over DAGs. Previous work established conditional lower bounds for solving k-DSP and its variants via reductions from detecting cliques in graphs. Prior work implied that k-Clique can be reduced to 2k-DSP in DAGs and undirected graphs with O((kn)²) nodes. We improve this reduction, by showing how to reduce from k-Clique to k-DSP in DAGs and undirected graphs with O((kn)²) nodes (halving the number of paths needed in the reduced instance). A variant of k-DSP is the k-Disjoint Paths (k-DP) problem, where the solution paths no longer need to be shortest paths. Previous work reduced from k-Clique to p-DP in DAGs with O(kn) nodes, for p = k + k(k-1)/2. We improve this by showing a reduction from k-Clique to p-DP, for p = k + ⌊k²/4⌋. Under the k-Clique Hypothesis from fine-grained complexity, our results establish better conditional lower bounds for k-DSP for all k ≥ 4, and better conditional lower bounds for p-DP for all p ≤ 4031. Notably, our work gives the first nontrivial conditional lower bounds 4-DP in DAGs and 4-DSP in undirected graphs and DAGs. Before our work, nontrivial conditional lower bounds were only known for k-DP and k-DSP on such graphs when k ≥ 6.
Cite as

Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ICALP.2024.9,
  author =	{Akmal, Shyan and Vassilevska Williams, Virginia and Wein, Nicole},
  title =	{{Detecting Disjoint Shortest Paths in Linear Time and More}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{9:1--9:17},
  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.9},
  URN =		{urn:nbn:de:0030-drops-201529},
  doi =		{10.4230/LIPIcs.ICALP.2024.9},
  annote =	{Keywords: disjoint shortest paths, algebraic graph algorithms, disjoint paths, fine-grained complexity, clique}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.7
Faster Detours in Undirected Graphs

Authors: Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The k-Detour problem is a basic path-finding problem: given a graph G on n vertices, with specified nodes s and t, and a positive integer k, the goal is to determine if G has an st-path of length exactly dist(s,t) + k, where dist(s,t) is the length of a shortest path from s to t. The k-Detour problem is NP-hard when k is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in f(k)poly(n) time, for f(⋅) as slow-growing as possible. We present faster algorithms for k-Detour in undirected graphs, running in 1.853^k poly(n) randomized and 4.082^kpoly(n) deterministic time. The previous fastest algorithms for this problem took 2.746^k poly(n) randomized and 6.523^k poly(n) deterministic time [Bezáková-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length k in undirected graphs [Björklund-Husfeldt-Kaski-Koivisto, JCSS 2017], intuitively by looking for paths of length k in randomly bipartitioned subgraphs. Our algorithms for k-Detour stem from a new application of this idea, which does not involve choosing the bipartitioned subgraphs randomly. Our work has direct implications for the k-Longest Detour problem, another related path-finding problem. In this problem, we are given the same input as in k-Detour, but are now tasked with determining if G has an st-path of length at least dist(s,t)+k. Our results for k-Detour imply that we can solve k-Longest Detour in 3.432^k poly(n) randomized and 16.661^k poly(n) deterministic time. The previous fastest algorithms for this problem took 7.539^k poly(n) randomized and 42.549^k poly(n) deterministic time [Fomin et al., STACS 2022].
Cite as

Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, and Zixuan Xu. Faster Detours in Undirected Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ESA.2023.7,
  author =	{Akmal, Shyan and Vassilevska Williams, Virginia and Williams, Ryan and Xu, Zixuan},
  title =	{{Faster Detours in Undirected Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.7},
  URN =		{urn:nbn:de:0030-drops-186601},
  doi =		{10.4230/LIPIcs.ESA.2023.7},
  annote =	{Keywords: path finding, detours, parameterized complexity, exact algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.8
A Local-To-Global Theorem for Congested Shortest Paths

Authors: Shyan Akmal and Nicole Wein

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Amiri and Wargalla proved the following local-to-global theorem about shortest paths in directed acyclic graphs (DAGs): if G is a weighted DAG with the property that for each subset S of 3 nodes there is a shortest path containing every node in S, then there exists a pair (s,t) of nodes such that there is a shortest st-path containing every node in G. We extend this theorem to general graphs. For undirected graphs, we prove that the same theorem holds (up to a difference in the constant 3). For directed graphs, we provide a counterexample to the theorem (for any constant). However, we prove a roundtrip analogue of the theorem which guarantees there exists a pair (s,t) of nodes such that every node in G is contained in the union of a shortest st-path and a shortest ts-path. The original local-to-global theorem for DAGs has an application to the k-Shortest Paths with Congestion c ((k,c)-SPC) problem. In this problem, we are given a weighted graph G, together with k node pairs (s_1,t_1),… ,(s_k,t_k), and a positive integer c ≤ k, and tasked with finding a collection of paths P_1,… , P_k such that each P_i is a shortest path from s_i to t_i, and every node in the graph is on at most c paths P_i, or reporting that no such collection of paths exists. When c = k, there are no congestion constraints, and the problem can be solved easily by running a shortest path algorithm for each pair (s_i,t_i) independently. At the other extreme, when c = 1, the (k,c)-SPC problem is equivalent to the k-Disjoint Shortest Paths (k-DSP) problem, where the collection of shortest paths must be node-disjoint. For fixed k, k-DSP is polynomial-time solvable on DAGs and undirected graphs. Amiri and Wargalla interpolated between these two extreme values of c, to obtain an algorithm for (k,c)-SPC on DAGs that runs in polynomial time when k-c is constant. In the same way, we prove that (k,c)-SPC can be solved in polynomial time on undirected graphs whenever k-c is constant. For directed graphs, because of our counterexample to the original theorem statement, our roundtrip local-to-global result does not imply such an algorithm (k,c)-SPC. Even without an algorithmic application, our proof for directed graphs may be of broader interest because it characterizes intriguing structural properties of shortest paths in directed graphs.
Cite as

Shyan Akmal and Nicole Wein. A Local-To-Global Theorem for Congested Shortest Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ESA.2023.8,
  author =	{Akmal, Shyan and Wein, Nicole},
  title =	{{A Local-To-Global Theorem for Congested Shortest Paths}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.8},
  URN =		{urn:nbn:de:0030-drops-186618},
  doi =		{10.4230/LIPIcs.ESA.2023.8},
  annote =	{Keywords: disjoint paths, shortest paths, congestion, parameterized complexity}
}
  • Refine by Type
  • 20 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 9 2025
  • 1 2024
  • 3 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 9 Akmal, Shyan
  • 4 Jin, Ce
  • 3 Vassilevska Williams, Virginia
  • 3 Williams, Ryan
  • 2 Choudhary, Keerti
  • Show More...

  • Refine by Series/Journal
  • 20 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Pattern matching
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 2 Fine-grained complexity
  • 2 Quantum Algorithms
  • 2 Quantum Computing
  • 2 disjoint paths
  • 2 dynamic programming
  • 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