Beer Path Problems in Temporal Graphs

Andrea D'Ascenzo; Anna Mpanti; Aris Pagourtzis; Christos Pergaminelis; Giuseppe F. Italiano; Sotiris Kanellopoulos

arxiv: 2507.08685 · v3 · submitted 2025-07-11 · 💻 cs.DS

Beer Path Problems in Temporal Graphs

Andrea D'Ascenzo , Giuseppe F. Italiano , Sotiris Kanellopoulos , Anna Mpanti , Aris Pagourtzis , Christos Pergaminelis This is my paper

Pith reviewed 2026-05-19 05:26 UTC · model grok-4.3

classification 💻 cs.DS

keywords beer pathstemporal graphstemporal path algorithmsearliest arrivallatest departuredynamic updatespoints of interest

0 comments

The pith

Temporal beer paths can be found with algorithms that match the speed of standard temporal path algorithms.

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

The paper defines beer paths in temporal graphs, where a path must visit at least one beer vertex that is active only at specific times, and edges carry time labels. It gives algorithms for the earliest-arrival, latest-departure, fastest, and shortest versions of these paths. These algorithms run in the same asymptotic time as ordinary temporal path algorithms on both edge-stream and adjacency-list inputs. A reader would care because many practical routing tasks combine scheduled connections with optional timed stops whose availability changes over time.

Core claim

We introduce the notion of temporal beer paths in graphs with time-dependent edges and beer vertices that activate only at certain times. We formally define the earliest-arrival, latest-departure, fastest, and shortest temporal beer path problems and give algorithms that solve each variant in time matching the best known algorithms for the corresponding non-beer temporal path problem. The algorithms work for input given as an edge stream or as an adjacency list. We further provide preprocessing methods that support efficient queries after dynamic changes such as new openings or closings of beer vertices, either by precomputing selected paths or by converting the temporal graph into an static

What carries the argument

Temporal beer path: a temporal path that visits at least one beer vertex at a time when that vertex is active.

If this is right

Earliest-arrival temporal beer paths are computable in the same time bound as ordinary earliest-arrival temporal paths.
The same complexity preservation holds for latest-departure, fastest, and shortest temporal beer paths.
Preprocessing or static-graph transformation lets the algorithms answer queries after beer-vertex activation times change.
The methods apply uniformly to both edge-stream and adjacency-list representations of the input.

Where Pith is reading between the lines

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

The same algorithmic pattern could be reused for other time-windowed points of interest such as charging stations or delivery lockers.
Implementation on real transit schedules with known shop hours would give a direct empirical check of the claimed complexity match.
The dynamic-update techniques may connect to online route planning where facilities open or close in real time.

Load-bearing premise

That standard temporal path algorithms already exist with known time complexities that the new beer-path algorithms can match without increasing the asymptotic cost.

What would settle it

A concrete temporal graph instance together with beer-vertex activation times on which any correct algorithm for temporal beer paths requires more than a constant-factor slowdown compared with the fastest known algorithm for the matching non-beer temporal path problem.

read the original abstract

Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures the option of visiting points of interest, such as gas stations or convenience stops, prior to reaching the final destination, has been recently introduced and extensively studied in static graphs. However, existing approaches do not account for temporal information, which is often crucial in real-world scenarios. For instance, transit services may follow fixed schedules, and shops may only be accessible during certain hours. In this work, we introduce the notion of beer paths in temporal graphs, where edges are time-dependent and certain vertices (beer vertices) are active only at specific time instances. We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms for these problems under both edge stream and adjacency list representations. The time complexity of each of our algorithms is aligned with that of corresponding temporal pathfinding algorithms, thus preserving efficiency. Additionally, we present preprocessing techniques that enable efficient query answering under dynamic conditions, for example new openings or closings of shops. We achieve this through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph.

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.

Desk Editor's Note private letter to a colleague

This paper defines four temporal beer-path problems and gives algorithms whose costs match the corresponding non-beer temporal path algorithms.

read the letter

The core contribution is a clean extension of beer paths—optional stops at time-activated vertices—to temporal graphs with time-labeled edges. The authors define earliest-arrival, latest-departure, fastest, and shortest versions and supply algorithms for both edge-stream and adjacency-list inputs. They also sketch preprocessing that supports dynamic changes to beer-vertex availability while staying in the same asymptotic regime as the static case. That complexity alignment is the main practical point: the beer condition folds into existing label or priority-queue updates without an extra factor in the big-O bound. The dynamic part uses either selected-path precomputation or a static-graph transformation, both standard tricks that can preserve efficiency if implemented carefully. The work is definitional and algorithmic rather than a new technique, but the reduction looks natural and the claims line up with prior temporal-path results. A minor soft spot is that the abstract leaves the exact update rules for beer visits implicit, so a referee would want to see the pseudocode or a worked example to confirm no hidden logarithmic overhead appears in the worst case. The dynamic preprocessing also needs explicit bounds on how often the precomputation must be redone. This paper is for researchers who already work on temporal networks and want a ready-made way to add optional timed stops. Anyone building scheduling tools for transit or delivery with flexible waypoints could find the problem statements useful. It is not foundational, but the extension is straightforward enough that the details are worth checking. I would send it to peer review; the central claim is plausible and the complexity preservation is worth verifying in full.

Referee Report

1 major / 2 minor

Summary. The paper introduces beer paths in temporal graphs, where edges have time labels and certain vertices (beer vertices) are active only at specific times. It formally defines four problems—earliest-arrival, latest-departure, fastest, and shortest temporal beer paths—and proposes algorithms for computing them under both edge-stream and adjacency-list input representations. The central claim is that each algorithm's time complexity aligns with that of the corresponding standard temporal pathfinding algorithm. The work also includes preprocessing techniques to support efficient queries under dynamic changes to beer-vertex activation times, such as new openings or closings.

Significance. If the complexity-alignment claims hold, the paper delivers a clean and practical extension of the beer-path concept to temporal settings, which is relevant for applications involving scheduled networks (e.g., transit with time-dependent stops). The approach of folding beer-vertex visits into existing temporal-search primitives while preserving asymptotic bounds is a natural and useful contribution. The dynamic-preprocessing component further increases applicability. The explicit complexity statements relative to prior temporal algorithms constitute a verifiable strength of the manuscript.

major comments (1)

[§4] §4 (Algorithms for edge-stream representation): the claim that the earliest-arrival beer-path algorithm runs in the same O(m log n) bound as the standard temporal earliest-arrival algorithm requires an explicit argument that the additional checks for beer-vertex activation times do not introduce extra logarithmic factors or extra traversals; the current sketch folds the check into the label update but does not quantify the cost of maintaining the activation-time data structure.

minor comments (2)

[Section 2] Section 2: the notation for beer-vertex activation intervals versus edge time labels is introduced without a consolidated table; adding a small comparison table would improve readability.
[Dynamic preprocessing] The dynamic-preprocessing section would benefit from a brief statement of the space overhead of the precomputed structures relative to the input size.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation for minor revision. The comment on the complexity analysis in §4 is well-taken, and we will strengthen the manuscript accordingly.

read point-by-point responses

Referee: [§4] §4 (Algorithms for edge-stream representation): the claim that the earliest-arrival beer-path algorithm runs in the same O(m log n) bound as the standard temporal earliest-arrival algorithm requires an explicit argument that the additional checks for beer-vertex activation times do not introduce extra logarithmic factors or extra traversals; the current sketch folds the check into the label update but does not quantify the cost of maintaining the activation-time data structure.

Authors: We agree that the current sketch in §4 would benefit from a more explicit complexity argument. In the revised manuscript we will add a dedicated paragraph immediately after the algorithm description that quantifies the cost: activation times for each beer vertex are stored in a sorted array (precomputed in a linear-time pass over the input), and the search processes events in non-decreasing time order. Consequently, a single monotonically advancing pointer per beer vertex suffices to determine the next activation time in amortized O(1) time per vertex examination. Because these pointer advances are charged to the O(m) edge examinations and never require binary search or additional priority-queue operations, the overall bound remains O(m log n) with no hidden logarithmic factors or extra traversals. revision: yes

Circularity Check

0 steps flagged

No significant circularity; definitional and algorithmic extension of external temporal path results

full rationale

The paper defines four temporal beer-path problems on time-labeled edges and time-activated beer vertices, then describes algorithms whose asymptotic costs are claimed to match those of standard temporal path algorithms under edge-stream and adjacency-list inputs. No equations, fitted parameters, or self-referential reductions appear; the claimed alignment is achieved by folding beer-vertex checks into existing priority-queue or label-update primitives from prior temporal-graph literature. Preprocessing for dynamic beer-vertex changes is likewise stated to preserve the same asymptotic regime relative to external benchmarks. The derivation chain is therefore self-contained and does not reduce any central claim to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on standard assumptions from temporal graph literature and introduces the new concept of beer vertices without additional fitted constants or physical entities.

axioms (1)

domain assumption Temporal graphs consist of edges with explicit time intervals or labels and vertices that may have activation times.
Invoked when defining temporal beer paths in the abstract.

invented entities (1)

Beer vertex no independent evidence
purpose: A vertex that is active only at specific discrete time instances and must be visited for the path to count as a beer path.
New modeling construct introduced to capture time-dependent points of interest.

pith-pipeline@v0.9.0 · 5768 in / 1146 out tokens · 40102 ms · 2026-05-19T05:26:54.320783+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We formally define the problems of computing earliest-arrival, latest-departure, fastest, and shortest temporal beer paths and propose efficient algorithms ... time complexity ... aligned with that of corresponding temporal pathfinding algorithms
IndisputableMonolith/Foundation/DimensionForcing.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We achieve this through appropriate precomputation of selected paths or by transforming a temporal graph into an equivalent static graph

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

Maximizing Reachability via Shifting of Temporal Paths
cs.DS 2026-05 unverdicted novelty 6.0

Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Shortest beer path queries in outerplanar graphs.Algorithmica, 85(6):1679–1705, December 2022.doi:10.1007/s00453-022-01045-4

1 Joyce Bacic, Saeed Mehrabi, and Michiel Smid. Shortest beer path queries in outerplanar graphs.Algorithmica, 85(6):1679–1705, December 2022.doi:10.1007/s00453-022-01045-4. 2 Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota. Graph spanners for group steiner distances. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Her...

work page doi:10.1007/s00453-022-01045-4 2022
[2]

3 Diego Caro, M

URL:https: //doi.org/10.4230/LIPIcs.ESA.2024.25,doi:10.4230/LIPICS.ESA.2024.25. 3 Diego Caro, M. Andrea Rodríguez, and Nieves R. Brisaboa. Data structures for temporal graphs based on compact sequence representations.Inf. Syst., 51:1–26,

work page doi:10.4230/lipics.esa.2024.25 2024
[3]

4David Coudert, Andrea D’Ascenzo, and Mattia D’Emidio

URL:https: //doi.org/10.1016/j.is.2015.02.002,doi:10.1016/J.IS.2015.02.002. 4David Coudert, Andrea D’Ascenzo, and Mattia D’Emidio. Indexing graphs for shortest beer path queries. In Paul C. Bouman and Spyros C. Kontogiannis, editors,24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2024, September 5-6,...

work page doi:10.1016/j.is.2015.02.002 2015
[4]

5 Rathish Das, Meng He, Eitan Kondratovsky, J

URL: https: //doi.org/10.4230/OASIcs.ATMOS.2024.2,doi:10.4230/OASICS.ATMOS.2024.2. 5 Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu. Shortest beer path queries in interval graphs. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 202...

work page doi:10.4230/oasics.atmos.2024.2 2024
[5]

6 Joachim Gudmundsson and Yuan Sha

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2022.59, doi:10.4230/LIPICS.ISAAC.2022.59. 6 Joachim Gudmundsson and Yuan Sha. Shortest beer path queries in digraphs with bounded treewidth. In Satoru Iwata and Naonori Kakimura, editors,34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan, volume 283 ofLIPIcs, ...

work page doi:10.4230/lipics.isaac.2022.59 2022
[6]

7 Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2023.35,doi:10.4230/LIPICS.ISAAC.2023.35. 7 Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest beer path queries based on graph decomposition. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto,...

work page doi:10.4230/lipics.isaac.2023.35 2023
[7]

8 Petter Holme

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2023.37, doi:10.4230/LIPICS.ISAAC.2023.37. 8 Petter Holme. Modern temporal network theory: a colloquium.The European Physical Journal B, 88:1–30,

work page doi:10.4230/lipics.isaac.2023.37 2023
[8]

Rossi, Nesreen K

12 John Boaz Lee, Giang Nguyen, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Dynamic node embeddings from edge streams.IEEE Trans. Emerg. Top. Comput. Intell., 5(6):931–946, 2021.doi:10.1109/TETCI.2020.3011432. 13 Othon Michail. An introduction to temporal graphs: An algorithmic perspective.Internet Math., 12(4):239–280, 2016.doi:10.1080...

work page doi:10.1109/tetci.2020.3011432 2021
[9]

16 Michael N

URL:https://doi.org/10.1016/j.ejor.2023.07.022,doi:10.1016/J.EJOR.2023.07.022. 16 Michael N. Rice and Vassilis J. Tsotras. Exact graph search algorithms for generalized traveling salesman path problems. In Ralf Klasing, editor,Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9,

work page doi:10.1016/j.ejor.2023.07.022 2023
[10]

17 Michael N

doi:10.1007/ 978-3-642-30850-5\_30. 17 Michael N. Rice and Vassilis J. Tsotras. Engineering generalized shortest path queries. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 949–960,

work page 2013
[11]

18SS Srivastava, Santosh Kumar, RC Garg, and Prasenjit Sen

doi:10.1109/ICDE.2013.6544888. 18SS Srivastava, Santosh Kumar, RC Garg, and Prasenjit Sen. Generalized traveling salesman problem through n sets of nodes.CORS journal, 7(2):97,

work page doi:10.1109/icde.2013.6544888 2013
[12]

1007/s41019-019-00105-0,doi:10.1007/S41019-019-00105-0

URL:https://doi.org/10. 1007/s41019-019-00105-0,doi:10.1007/S41019-019-00105-0. 20 Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs.Proc. VLDB Endow., 7(9):721–732, May 2014.doi:10.14778/2732939. 2732945. 21 Tianming Zhang, Yunjun Gao, Jie Zhao, Lu Chen, Lu Jin, Zhengyi Yang, Bin Cao, and Jing Fan. Ef...

work page doi:10.1007/s41019-019-00105-0 2014

[1] [1]

Shortest beer path queries in outerplanar graphs.Algorithmica, 85(6):1679–1705, December 2022.doi:10.1007/s00453-022-01045-4

1 Joyce Bacic, Saeed Mehrabi, and Michiel Smid. Shortest beer path queries in outerplanar graphs.Algorithmica, 85(6):1679–1705, December 2022.doi:10.1007/s00453-022-01045-4. 2 Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota. Graph spanners for group steiner distances. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Her...

work page doi:10.1007/s00453-022-01045-4 2022

[2] [2]

3 Diego Caro, M

URL:https: //doi.org/10.4230/LIPIcs.ESA.2024.25,doi:10.4230/LIPICS.ESA.2024.25. 3 Diego Caro, M. Andrea Rodríguez, and Nieves R. Brisaboa. Data structures for temporal graphs based on compact sequence representations.Inf. Syst., 51:1–26,

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

[3] [3]

4David Coudert, Andrea D’Ascenzo, and Mattia D’Emidio

URL:https: //doi.org/10.1016/j.is.2015.02.002,doi:10.1016/J.IS.2015.02.002. 4David Coudert, Andrea D’Ascenzo, and Mattia D’Emidio. Indexing graphs for shortest beer path queries. In Paul C. Bouman and Spyros C. Kontogiannis, editors,24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2024, September 5-6,...

work page doi:10.1016/j.is.2015.02.002 2015

[4] [4]

5 Rathish Das, Meng He, Eitan Kondratovsky, J

URL: https: //doi.org/10.4230/OASIcs.ATMOS.2024.2,doi:10.4230/OASICS.ATMOS.2024.2. 5 Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Anurag Murty Naredla, and Kaiyu Wu. Shortest beer path queries in interval graphs. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 202...

work page doi:10.4230/oasics.atmos.2024.2 2024

[5] [5]

6 Joachim Gudmundsson and Yuan Sha

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2022.59, doi:10.4230/LIPICS.ISAAC.2022.59. 6 Joachim Gudmundsson and Yuan Sha. Shortest beer path queries in digraphs with bounded treewidth. In Satoru Iwata and Naonori Kakimura, editors,34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto, Japan, volume 283 ofLIPIcs, ...

work page doi:10.4230/lipics.isaac.2022.59 2022

[6] [6]

7 Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2023.35,doi:10.4230/LIPICS.ISAAC.2023.35. 7 Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest beer path queries based on graph decomposition. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation, ISAAC 2023, December 3-6, 2023, Kyoto,...

work page doi:10.4230/lipics.isaac.2023.35 2023

[7] [7]

8 Petter Holme

URL: https://doi.org/10.4230/LIPIcs.ISAAC.2023.37, doi:10.4230/LIPICS.ISAAC.2023.37. 8 Petter Holme. Modern temporal network theory: a colloquium.The European Physical Journal B, 88:1–30,

work page doi:10.4230/lipics.isaac.2023.37 2023

[8] [8]

Rossi, Nesreen K

12 John Boaz Lee, Giang Nguyen, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Dynamic node embeddings from edge streams.IEEE Trans. Emerg. Top. Comput. Intell., 5(6):931–946, 2021.doi:10.1109/TETCI.2020.3011432. 13 Othon Michail. An introduction to temporal graphs: An algorithmic perspective.Internet Math., 12(4):239–280, 2016.doi:10.1080...

work page doi:10.1109/tetci.2020.3011432 2021

[9] [9]

16 Michael N

URL:https://doi.org/10.1016/j.ejor.2023.07.022,doi:10.1016/J.EJOR.2023.07.022. 16 Michael N. Rice and Vassilis J. Tsotras. Exact graph search algorithms for generalized traveling salesman path problems. In Ralf Klasing, editor,Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9,

work page doi:10.1016/j.ejor.2023.07.022 2023

[10] [10]

17 Michael N

doi:10.1007/ 978-3-642-30850-5\_30. 17 Michael N. Rice and Vassilis J. Tsotras. Engineering generalized shortest path queries. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 949–960,

work page 2013

[11] [11]

18SS Srivastava, Santosh Kumar, RC Garg, and Prasenjit Sen

doi:10.1109/ICDE.2013.6544888. 18SS Srivastava, Santosh Kumar, RC Garg, and Prasenjit Sen. Generalized traveling salesman problem through n sets of nodes.CORS journal, 7(2):97,

work page doi:10.1109/icde.2013.6544888 2013

[12] [12]

1007/s41019-019-00105-0,doi:10.1007/S41019-019-00105-0

URL:https://doi.org/10. 1007/s41019-019-00105-0,doi:10.1007/S41019-019-00105-0. 20 Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path problems in temporal graphs.Proc. VLDB Endow., 7(9):721–732, May 2014.doi:10.14778/2732939. 2732945. 21 Tianming Zhang, Yunjun Gao, Jie Zhao, Lu Chen, Lu Jin, Zhengyi Yang, Bin Cao, and Jing Fan. Ef...

work page doi:10.1007/s41019-019-00105-0 2014