ALT Temporal graphs are graphs whose edge relation changes in discrete time steps. The Temporal Exploration Problem (TEXP) asks for a temporal walk that visits all vertices. We show that every connected temporal graph with n vertices can be explored in O(qnlog³(n)) time steps, where q is the number of vertex color classes induced by the 2-dimensional Weisfeiler-Leman (2-WL) coloring. For small q, our bound substantially improves on the known worst-case bound of Θ(n²) in general connected temporal graphs. A corresponding walk can be constructed in deterministic polynomial time. The upper bound is complemented by lower bounds of Ω(nlog(n)) when q is constant and Ω(qn) when 1 ≤ q ≤ n. We also apply our techniques to the Temporal Rendezvous Problem (TRP), in which two agents that do not communicate have to meet on a vertex of the temporal graph. Our exploration algorithm yields that, with only polynomial-time computational power, the agents can meet in O(nlog³(n)) time steps, leaving a gap of

ALT The non-preemptive dial-a-ride problem (DaRP) asks for a minimum-cost route of a capacitated vehicle that serves a collection of pickup-and-delivery requests, without allowing objects to be transferred or temporarily unloaded. We study this problem and the closely related minimum-ratio Steiner k-Forest (SkF) in general symmetric metrics on n locations. We develop a randomized polynomial-time algorithm with expected approximation ratio O(n¹/4log¹1n) for the minimum-ratio SkF. Our algorithm combines a deterministic approximation on hierarchically well-separated trees with randomized metric embeddings. Using this algorithm, we obtain expected O(n¹/4log¹2n)-approximations for both the non-preemptive DaRP and the SkF. These guarantees improve on the previous n⁰.3+ε-approximation ratios for the SkF and the non-preemptive DaRP, where ε>0 is any fixed constant. Complementing these algorithmic results, we establish the first superconstant inapproximability bounds for the non-preemptive DaRP. Un

ALT Power grids use a constantly changing mix of fossil fuels and clean renewables like solar and wind. Because of this, the carbon footprint fluctuates drastically based on time and geographic location. Time-varying carbon intensity creates opportunities to reduce carbon emissions by shifting workloads to cleaner periods, but deadlines, task dependencies, and limited edge capacity constrain this flexibility. We study carbon-aware scheduling of jobs with release times, deadlines, and arbitrary precedence constraints under piecewise-constant carbon costs. Jobs execute preemptively on a single edge server or are outsourced at job-dependent costs to an unlimited-capacity cloud, modeled as providing instantaneous execution. The objective is to minimize the sum of edge carbon costs and cloud outsourcing costs while satisfying all timing and precedence constraints. For edge-only execution, we give an exact polynomial-time algorithm. Allowing cloud outsourcing makes the problem NP-hard, but we ob

ALT The k-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select k centers such that the maximum distance from any object to its closest center is minimized. The k-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for k-center clustering in metric spaces, a comprehensive experimental comparison of graph-based k-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2

ALT Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on

ALT An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative stretch k. The classical oracle of Thorup and Zwick [STOC'01, JACM'05] has stretch k=2ℓ-1 and uses O(ℓ n¹⁺¹/ℓ) space, for every integer ℓ≥1, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs (m=O(n)), their lower bound yields nothing beyond Ω(m) space. A pivot-based 1-hop ADO gives every vertex Õ(1) pivots and returns as an estimate the length of a walk of the form u→ pᵤ → pᵥ → v, where pᵤ is a pivot of u, pᵥ is a pivot of v, and pᵤ→ pᵥ is a stored distance. We observe that all the state-of-the-art ADOs with Õ(1) query time are in fact pivot-based 1-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every pivot-based 1-hop ADO with stretch k requires Ω̃(m¹⁺²/⁽ᵏ⁺¹)) space, for every real k≥1. This matches the best known upper bound

ALT In STOC 1972, Jürg Nievergelt and Edward M. Reingold introduced the BB[α]-tree, also known as a weight-balanced tree, which for any α ∈ (0,¹⁄₂] is a binary search tree where every node with induced subtree size s has children with induced subtree sizes at least α(s+1)-1. A new rotation-based binary search tree, the PopTree, is introduced. The PopTree stores n elements and is a BB[tfrac120]-tree after the execution of each search and a BB[tfrac1729]-tree at all times, notably while rebalancing. For any constant α, its performance on search sequences of length Ω(n log n) is proved to be within a constant factor (which can depend on α) of the optimal offline rotation-based binary search tree that maintains the BB[α] balance invariant.

ALT The Fréchet distance (also known as the dog-leash distance) is a well-studied and prevalent distance measure for polygonal curves. In this paper we present parallel algorithms for computing the discrete frechet{ dis}tance between two curves, in both the PRAM and MPC models. For two polygonal curves of length n, we show that the distance between them can be computed in the PRAM model in O(log n/ σ) rounds and Õ(n²⁺σ) total work for any 0<σ<1. In the sublinear MPC model with nρ space per machine, it can be computed in O(log n / ρ²) rounds and Õ(n²⁺ρ) total space. For c-packed curves, we match our bounds to the sequential algorithms, showing that a (1+\eps)-approximation of the distance can be computed in the PRAM model in O(logn+1/σ³) rounds and Õ(n¹⁺σ) total work, and in the sublinear MPC model in O(1 /ρ³) rounds and Õ(n¹⁺ρ) total space, for any constant \eps>0. As part of our algorithms for c-packed curves, we also present parallel algorithms for computing curve simplifications, which

ALT We study Largest Cardinality Subset Sum (LCSS): given n nonnegative integers and a target t, compute a subset summing to t with maximum cardinality. We also consider its all-targets version (ATLCSS), which asks for this maximum for every sum s∈{1,…,t}. The LCSS problem sits squarely between the subset sum and the knapsack problem. A straightforward dynamic-programming algorithm runs in time O(nt) and solves ATLCSS, and using Jin and Bringmann (both in STOC 2024, independent work) 0-1 knapsack results we achieve a Õ(n + aₘₐₓ²)-time deterministic algorithm for LCSS. Our main result is a randomized Õ(n+√n t)-time algorithm for LCSS. Then, we complement this result with a randomized Õ(n+t³/²)-time algorithm for ATLCSS. Together, our two algorithms give a Õ(n+tmin{√n,√t})-time algorithm for LCSS. As an application of ATLCSS, we solve the search version of Projection Subset Sum, introduced by Dutta and Rajasree (SYNSAC 2023), in Õ(n+t³/²) time for every fixed ℓₚ norm with p≥ 1. For ℓ₁,

ALT We study labeling schemes for p × q Γ-free binary matrices, which do not contain a submatrix of the form Γ = 1 1 1 0. We give a labeling scheme that uses O(log² N)-bit labels for rows and columns, where N=p+q, such that any matrix entry can be determined from the corresponding two labels in constant time in the word RAM model. The worst-case label size matches the counting lower bound up to constant factors. We also show that the entrywise least Γ-free supermatrix of an arbitrary p× q binary matrix, together with its labels, can be constructed in O(pq) time. Our construction represents a Γ-free matrix by a sequence of rooted forests, where each column corresponds to a node and the 1-entries of each row form a root path in its corresponding forest. For n-vertex strongly chordal and chordal bipartite graphs, our result gives asymptotically optimal O(log² n)-bit adjacency labeling schemes with constant-time queries. These results answer both representation questions posed by Spinrad in 19

ALT We study the problem of characterizing the optimal consistency–robustness tradeoff for single-machine non-clairvoyant scheduling with predicted processing times. For a fixed number of jobs n, Wei and Zhang (2020) established a lower bound on the achievable consistency–robustness tradeoff which is known to be tight only in a few restrictive cases, leaving the optimal tradeoff for general n unresolved. A different worst-case-n regime was introduced by Benomar et al. (2025), who applied the former work's construction to show that for λ ∈ (0, 1), any (1+λ)-consistent algorithm must be 1 + Ω(√(1/λ))-robust. On the other hand, the best known upper bound gives (1+λ)-consistency and 1+O(1/λ)-robustness, leaving a polynomial gap. In this work, we develop a new lower bound using a multi-stage adversarial construction and a new algorithm that together give a near-optimal characterization of the consistency–robustness tradeoff: for every n, our upper bound is within a multiplicative factor 3/2 of

ALT In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., O(m+n)) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for example it is possible to find a minimum dominating set in an interval graph in O(n) time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in O(nlog n) time if a suitably small representation is given. In this paper, we reduce the runtime to O(n). Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for Matching) a Union-Find data structure.

ALT We study deterministic gossiping in unknown strongly connected directed radio networks with n vertices, m arcs, and distinct identifiers in {1,…,N}, where N=n^O(1). Messages are unrestricted; collision detection is unavailable. Our protocol combines amplified reception certificates, adaptive pruning, and permutation selectors. Each pruning iteration costs O(nlog²nloglog n) rounds. A two-step quadratic contraction limits each receiver and each class of identical closed in-neighborhoods to O(loglog n) qualifying selections. Under an explicit degree-concentration condition, our protocol takes O(mlog²n(loglog n)²) rounds. For directed regular graphs with common in- and out-degree Δ, our strategy achieves Õ(min{n√Δ,n²/Δ}), extending the identifier range of Wu and Chrobak and improving their high-degree bound. At completion entry, let a≥1 count original sources not yet credited as globally disseminated. Permutation selectors reduce our balanced completion budget by a factor of log²/3(a+1) r

ALT We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form A=KCK⁻¹ of a dynami

ALT We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules: Instead of outputting a single schedule, we seek a collection of schedules with provable makespan guarantees and substantially different job assignments. Committing to a single schedule in advance may be undesirable. Processing times may be uncertain, and constraints or domain knowledge may emerge later, so k schedules of similar quality offer meaningful alternatives. We measure pairwise diversity by the weighted Hamming distance between job assignments and study the two standard objectives in the diverse-solutions literature: max-sum diversity, which maximizes the total pairwise distance between schedules, and max-min diversity, which maximizes the smallest pairwise distance. For the max-sum objective, we show that optimal diversity can be achieved in polynomial time without sacrificing the classic makespan approximation factor. For every feasible makespan target T, we can

ALT In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set V of n clients with normalized demands dᵥ ∈ (0,1], a depot r, a unit vehicle capacity, and symmetric metric travel costs c on V ∪ {r}. We seek a collection of routes of minimum total cost that start and end at r, serve each client's entire demand on a single route, and respect the unit capacity constraint ∑ᵥ∈V(R) dᵥ ≤ 1 on every route R, where V(R) denotes the clients served by R. This models deliveries from a common depot in which each customer's order must be delivered in a single trip. UCVRP generalizes the metric traveling salesman problem (TSP) and is therefore NP-hard. Capacity constraints add a packing difficulty: when all clients are colocated away from the depot, minimizing the route cost is equivalent to minimizing the number of bins in bin packing. Consequently, UCVRP admits no polynomial-time approximation ratio below 3/2 unless P=NP (Grandoni, Mathieu, and Zhou, 2023). The classical 3.5-app

ALT In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately. The question is which of two terminals the token reaches first. ARRIVAL lies in NP \cap coNP, but no polynomial-time algorithm is known.The fastest known algorithms turn some vertices into terminals and search for consistent guesses of the numbers of tokens that these vertices send out. The first, due to G\"artner et al. [ICALP 2021], searches all vertices at once with an algorithm for fixed points of monotone maps, and the second, due to Haslebacher [ICALP 2025], searches one vertex at a time by binary search. Both search for a fixed point of the same map, which returns how many tokens arrive at the guessed vertices. We guess the vertices in blocks of k, between these two extremes, which needs a search in k dimensions with few evaluations of this map. To do so, we build on the connection between ARRIVAL and \ell₁-contractions establi

ALT We study the Monitoring Edge-Geodetic Set problem (MEG-Set), which asks for a minimum-cardinality set M of vertices of an undirected graph G of n vertices such that every edge of G belongs to all shortest paths between some pair of vertices in M. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time O(n¹/3log²/3n)-approximation algorithm, improving upon the previously best-known O(√(nlog n)) approximation ratio. On the negative side, for every constant ε ∈ (0,1), we prove that the problem admits no polynomial-time (2^{log¹-ε n})-approximation algorithm, unless NP⊆ DTIME(n^polylogn). This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that megset is NP-hard on planar 2-degenerate graphs, whereas NP-hardness was previously known for 1-apex 2-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance prese

ALT The Minimum Shared-Power Edge Cut (MSPEC) problem seeks to disconnect two designated terminals with minimum total power by assigning powers to graph vertices and deleting every edge for which the sum of the powers at its endpoints reaches its edge weight. Previous work gave a fully polynomial-time approximation scheme for this problem, while its exact computational complexity remained open. We prove that general MSPEC with nonnegative edge weights can be solved exactly in polynomial time. Specifically, we first use linear programming duality for each fixed cut to reformulate MSPEC as minimizing the maximum terminal-relaxed matching weight over all s-t cuts. Then, we construct a terminal-copy extended graph that transforms the maximum-weight matching model with unconstrained terminal capacities for a fixed cut into an equivalent ordinary maximum-weight matching model. Next, we extend the submodularity of the unweighted maximum-matching cut function to nonnegative edge weights and prove

ALT The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a 1/2-approximation guarantee in general graphs and a 2/3 guarantee in graphs with a perfect matching. We present a 2/3-approximation algorithm running in O(n⁵) time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least 2/3 of the optimum, and we give an example showing that this bound is tight.