We present our approach for the CG:SHOP 2026 challenge. In this international challenge, the goal was to find a median triangulation for a set of triangulations in the parallel flip reconfiguration graph of all triangulations of an underlying point set. Our simulated-annealing-based approach makes use of two ingredients: a heuristic edge selection for approximating the parallel flip distance of two given triangulations, and a heuristic procedure to generate good initial triangulations.

This repository contains benchmark instances for (s,t)-max-flow/min-cut, which were submitted to the 13th DIMACS Implementation Challenge. The instances are derived from the bicriteria polygon aggregation problem, which is studied in the following publications: Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach. Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert. In: ACM Transactions on Spatial Algorithms and Systems, vol. 11(1), ACM, pages 3:1--3:23, 2025. A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order. Arne Beines, Michael Kaibel, Philip Mayer, Petra Mutzel, Jonas Sauer. In: Proceedings of the 27th Workshop on Algorithm Engineering and Experiments (ALENEX'25), SIAM, pages 29--41, 2025. Bicriteria Polygon Aggregation with Arbitrary Shapes. Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer. To appear in: Proceedings of the 34th Annual European Symposium on Algorithms (ESA'26), Leibniz International Proceedings in Informatics, 2026. Background These instances are derived from a real-world application: polygon aggregation for map simplification. Given is a set $P$ of building footprints, represented as 2D polygons. The objective is to find a set $S$ of interior-disjoint representative regions, such that each polygon in $P$ is fully contained in a region of $S$. We are interested in a solution that minimizes the objective function $g_\alpha(S) = A(S) + \alpha \cdot P(S)$, where $A(S)$ and $P(S)$ are the total area and perimeter of the regions in $S$, respectively. The parameter $\alpha$ controls the trade-off between faithfulness to the input (represented by the area) and shape simplicity (represented by the perimeter). In a cartographic application, it can be thought of as the "zoom factor" -- the further we zoom out, the simpler we want the shapes to become. We distinguish between two variants of the problem, both for a fixed choice of $\alpha$: Subdivision-based: A subdivision $D$ of the plane (e.g., a constrained Delaunay triangulation) is supplied in advance, such that each polygon in $P$ appears as a cell of $D$. The solution must be constructed by selecting cells from $D$ to add to $P$. The problem is solved via a transformation to (s,t)-min-cut on an augmented geometric dual of $D$ (see any of the papers listed above for details). Unrestricted: No restrictions are made regarding the shape of $S$ -- the only conditions are that $P$ must be covered and that the objective function $g_\alpha(S)$ is minimized. Blank et al. show that in this variant, the polygons are connected by circular arcs of radius $\alpha$ that fulfill several other conditions. The arcs are chosen from a set of $O(n^2)$ candidates. The problem can then be solved optimally via a transformation to the subdivision-based case, where the subdivision $D$ is created by superimposing all $O(n^2)$ arcs. This yields a solution in polynomial time, although the subdivision is much more complex than the constrained Delaunay triangulation. The resulting instances have some similarities with grid-based computer vision max-flow instances, which are built using a similar geometric-dual construction: They are sparse and have short (s,t)-paths. However, unlike typical vision instances, they do not have a regular structure because they are derived from human settlement areas. Consequently, although all nodes (except for s and t) have low degrees, the degrees are not entirely uniform. For the unrestricted variant, the graph is highly detailed because it is derived from a geometric intersection process between many circular arcs. As a side note, a parametric version of the problem, where $\alpha$ is not fixed, has also been studied. Here, the objective is to find an optimal solution for every possible value of $\alpha$. Beines et al. show that, with an equivalent reformulation of the objective function $g_\alpha$, this is a monotone parametric min-cut problem. The instances in this dataset are not parametric, but parametric instances can be found here. Contents The dataset is split into two groups, depending on how the subdivision was built: triangulations: Using a constrained Delaunay triangulation, as proposed by Rottmann et al. The instances are cities of varying sizes (Bonn, Cologne, Berlin, Miami) and the entire German state of Saarland. For each instance, there are five copies, with the different $\alpha$ values 100, 500, 1000, 5000, and 25000. Note that the graph structure is the same for all copies; only the weights are different. arcs: Using the geometric intersection of the candidate arcs, as proposed by Blank et al. for the unrestricted variant. The instances represent the towns of Ahrem, Edendorf, Friesheim and Gerolstein in the German state of North Rhine-Westphalia. For each instance, there are four copies, with the different $\alpha$ values 100, 500, 1000, 5000. Note that for this variant, the graph size increases dramatically with $\alpha$. The arc capacities represent a weighted tradeoff between area and perimeter, measured in square decimeters (dm^2) and rounded to the nearest integer. The $\alpha$ parameter is also measured in decimeters. In the arcs instances, this corresponds to the radii of the circular arcs from which the subdivision is formed, e.g., $\alpha=5000$ represents arcs with radii of 500m. Data Sources Ahrem, Friesheim, Edendorf, Gerolstein, Bonn, Cologne: OpenStreetMap data from Geofabrik Saarland: OpenStreetMap data from Geofabrik Berlin, Miami: GHS-OBAT project Format The files follow the format from the first DIMACS implementation challenge. This is a text format in which each line is prefixed with a character that specifies the type of line. Lines starting with c are comments and should be ignored. The first non-comment line is the problem line: p max NODES ARCS Here, max is the problem type (max-flow/min-cut), NODES is the number of nodes in the network, and ARCS is the number of directed arcs. This is followed by two node descriptor lines:n IDT tn IDS s Here, IDT is the id of the sink node and IDS is the id of the source node. Note that in this format, node ids start at 1. Finally, there is an arc descriptor line for every directed arc in the network: a SRC DST C This specifies an arc from node SRC to DST with capacity C. Capacities with values of int32_max or more should be interpreted as infinite. Note that the format does not require that a reverse arc exists for every directed arc. If reverse arcs are required by your algorithm, you must ensure that missing arcs are added with capacity 0. Credits and Contact This dataset was created by two research groups at the University of Bonn: the geoinformation group headed by Prof. Dr. Jan-Henrik Haunert and the Computational Analytics group headed by Prof. Dr. Petra Mutzel. It is released under the MIT license. When using it, please cite the publications listed above. If you want to report problems or give feedback on the dataset, please contact Jonas Sauer ([email protected]).

We present T-REX (Transfer-Ranked EXploration), a new algorithm for journey planning in public transit networks on the country and continental scale. Our algorithm applies the principles of multi-level overlays to Trip-Based Public Transit Routing (TB). Using a multi-level partition of the network, T-REX identifies transfers between trips that are relevant for long-distance travel in a short precomputation phase. This information is then used to prune irrelevant local transfers during a query. Like other state-of-the-art algorithms, T-REX Pareto-optimizes arrival time and the number of used trips. T-REX dramatically outperforms previous overlay-based algorithms for three key reasons: (1) a better partition, (2) reducing the search space by focusing on transfers rather than trips, and (3) a redesigned query algorithm with improved memory efficiency and throughput. As a result, T-REX answers queries in less than 10ms on a network of Europe, including local and long-distance transit. This constitutes a speedup of 20 compared to TB and 80 compared to algorithms without preprocessing. The memory footprint is moderate and the precomputation takes only two minutes, while real-time schedule updates can be incorporated in a few seconds. These properties make T-REX the first public transit journey planning algorithm that fulfills the requirements of interactive real-time applications on the continental scale.

An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting. Our second and main set of results for the expiration model designs algorithms for the diameter and k-center problems, where items are points in a metric space. Our results significantly extend those known for the special case of sliding-window streams by Cohen-Addad, Schwiegelshohn, and Sohler [ICALP 2016], and obtain a strictly better approximation factor for the diameter in the important special case of high-dimensional Euclidean metrics. We develop new decomposition and coordination techniques along with a geometric dominance framework to filter out redundant points based on both temporal and spatial proximity.

We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective is to find the set of breakpoints, i.e., the points at which the minimum cut changes. It is well known that this problem can be solved in the same asymptotic runtime as the static minimum cut problem. However, existing algorithms that achieve this runtime bound involve fairly complicated steps that are inefficient in practice. PBFS uses a simpler approach that discovers the breakpoints in ascending order, which allows it to achieve the desired runtime bound while still performing well in practice. We evaluate our algorithm on benchmark instances from polygon aggregation and computer vision. Polygon aggregation was recently proposed as an application for parametric minimum cut, but the monotonicity property has not been exploited fully. PBFS outperforms the state of the art on most benchmark instances, usually by a factor of 2–3. It is particularly strong on instances with many breakpoints, which is the case for polygon aggregation. Compared to the existing min-cut-based approach for polygon aggregation, PBFS scales much better with the instance size. On large instances with millions of vertices, it is able to compute all breakpoints in a matter of seconds.

We study journey planning in multimodal networks consisting of public transit plus an unrestricted transfer mode (e.g., walking, cycling, e-scooter). In order to provide good results in practice, algorithms must account for vehicle delays. Delay-responsive algorithms receive a continuous stream of delay updates and must return optimal journeys in the currently known delay scenario. Updates are incorporated in an update phase, which must be fast (e.g., a few seconds). The fastest known approach for multimodal journey planning is ULTRA, which precomputes shortcuts representing transfers between vehicles. This allows query algorithms to find Pareto-optimal journeys regarding arrival time and the number of public transit trips without any performance loss compared to pure public transit networks. However, the precomputation phase does not account for delays and is too slow to rerun during the update phase. We present Delay-ULTRA, a delay-responsive variant of ULTRA. Since accounting for all theoretically possible delays would yield an impractically large set of shortcuts, our approach pre- computes shortcuts that are provably sufficient as long as delays do not exceed a configurable limit (e.g., 5 minutes). To handle delays above the limit (which are less frequent in practice), we propose a heuristic search for missing shortcuts that is fast enough to be run during the update phase. Our experimental evaluation on real-world data shows that Delay-ULTRA has extremely low error rates, failing to find less than 0.02% of optimal journeys on metropolitan and mid-sized country networks, and 0.16% on the much larger Germany network. Considering that the delay information that is available in realistic applications is never perfectly accurate or up to date, these error rates are negligible. Query speed is at most twice as slow as ULTRA without delay information, and up to 8 times faster than the fastest exact algorithm, which does not require a preprocessing phase.

This paper proposes multiple extensions to the popular bicriterion transit routing approach -- Trip-Based Transit Routing (TBTR). Specifically, building on the premise of the HypRAPTOR algorithm, we first extend TBTR to its partitioning variant -- HypTBTR. However, the improvement in query times of HyTBTR over TBTR comes at the cost of increased preprocessing. To counter this issue, two new techniques are proposed -- a One-To-Many variant of TBTR and multilevel partitioning. Our One-To-Many algorithm can rapidly solve profile queries, which not only reduces the preprocessing time for HypTBTR, but can also aid other popular approaches such as HypRAPTOR. Next, we integrate a multilevel graph partitioning paradigm in HypTBTR and HypRAPTOR to reduce the fill-in computations. The efficacy of the proposed algorithms is extensively tested on real-world large-scale datasets. Additional analysis studying the effect of hypergraph partitioning tools (hMETIS, KaHyPar, and an integer program) along with different weighting schemes is also presented.

We study the journey planning problem for multimodal networks consisting of public transit and a non-schedule-based transfer mode (e.g., walking, bicycle, e-scooter). So far, all efficient algorithms for this problem either restrict usage of the transfer mode or Pareto-optimize only two criteria: arrival time and the number of used public transit trips. However, we show that both limitations must be lifted in order to obtain high-quality solutions. In particular, the time spent using the (unrestricted) transfer mode must be optimized as a third criterion. We present McTB, the first algorithm that optimizes three criteria efficiently by avoiding costly data structures for maintaining Pareto sets. To enable unlimited transfers, we combine it with a three-criteria extension of the ULTRA [3, 16] preprocessing technique. Furthermore, since full Pareto sets become impractically large for more than two criteria, we adapt an approach by Delling et al. [5] to restrict the Pareto set in a methodical manner. Extensive experiments on real-world data show that our algorithms are fast enough for interactive queries even on large country-sized networks. Compared to the state of the art for multicriteria multimodal journey planning, MCR [6], we achieve a speedup of up to 80.

We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.

We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing [Witt, 2015]. However, this algorithm cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA [Baum et al., 2019], a preprocessing technique that allows any public transit algorithm that requires transitive transfers to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR.

We study multi-modal route planning in a network comprised of schedule-based public transportation, unrestricted walking, and cycling with bikes available from bike sharing stations. So far this problem has only been considered for scenarios with at most one bike sharing operator, for which MCR is the best known algorithm [Delling et al., 2013]. However, for practical applications, algorithms should be able to distinguish between bike sharing stations of multiple competing bike sharing operators. Furthermore, MCR has recently been outperformed by ULTRA for multi-modal route planning scenarios without bike sharing [Baum et al., 2019]. In this paper, we present two approaches for modeling multi-modal transportation networks with multiple bike sharing operators: The operator-dependent model requires explicit handling of bike sharing stations within the algorithm, which we demonstrate with an adapted version of MCR. In the operator-expanded model, all relevant information is encoded within an expanded network. This allows for applying any multi-modal public transit algorithm without modification, which we show for ULTRA. We proceed by describing an additional preprocessing step called operator pruning, which can be used to accelerate both approaches. We conclude our work with an extensive experimental evaluation on the networks of London, Switzerland, and Germany. Our experiments show that the new preprocessing technique accelerates both approaches significantly, with the fastest algorithm (ULTRA-RAPTOR with operator pruning) being more than an order of magnitude faster than the basic MCR approach. Moreover, the ULTRA preprocessing step also benefits from operator pruning, as its running time is reduced by a factor of 14 to 20.

We study a multi-modal route planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or taxis). The objective is to compute all journeys that are Pareto-optimal with respect to arrival time and the number of required transfers. While various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. As a result, even walking between stops is typically limited by a maximal duration or distance, or by requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called ULTRA (UnLimited TRAnsfers): Given a complete transfer graph (without any limitations, representing an arbitrary non-schedule-based mode of transportation), we compute a small number of transfer shortcuts that are provably sufficient for computing all Pareto-optimal journeys. We demonstrate the practicality of our approach by showing that these transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-Query algorithm family. Our extensive experimental evaluation shows that ULTRA is able to improve these algorithms from limited to unlimited transfers without sacrificing query speed, yielding the fastest known algorithms for multi-modal routing. This is true not just for walking, but also for other transfer modes such as cycling or driving.

We study the problem of computing public transit traffic assignments in a multi-modal setting: Given a public transit timetable, an additional unrestricted transfer mode (e.g., walking), and a set of origin-destination pairs, we aim to compute the utilization of all vehicles. While it has been shown that unrestricted walking can significantly improve journeys, computing such journeys efficiently remains algorithmically challenging. Since traffic assignments require the computation of millions of shortest paths, using a multi-modal network has previously not been feasible. In this work we combine the novel ULTRA [2] approach, which enables UnLimited TRAnsfers at the cost of a short preprocessing phase, with a state-of-the-art assignment algorithm, making multi-modal assignments practical. Careful algorithm engineering results in an efficient assignment algorithm, which even outperforms the algorithm it is based on, while enabling unlimited walking for the first time. Finally, we evaluate our algorithm on real worl data, where it computes over 15 million journeys in less than 17 seconds, showing its efficiency.

In route planning for electric vehicles (EVs), consumption profiles are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for EVs. In this work, we show that the complexity of a profile is at most linear in the graph size. Based on this insight, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. Exploiting efficient profile search, our approach also allows partial recharging at charging stations to save energy. In a sense, our results close the gap between efficient techniques for energy-optimal routes (based on simpler models) and NP-hard time-constrained problems involving charging stops for EVs. We propose a practical implementation, which we carefully integrate with Contraction Hierarchies and A* search. Even though the practical variant formally drops correctness, a comprehensive experimental study on a realistic, large-scale road network reveals that it always finds the optimal solution in our tests and computes even long-distance routes with charging stops in less than 300 ms.