CS Paper Radar

Towards Dynamic Top-$k$ Simple Shortest Paths

Gianlorenzo D'Angelo, Andrea D'Ascenzo, Mattia D'Emidio, Gabriele Di Stefano, Marta Innamorati

cs.DS ·submitted 2026-10-14 12:03 UTC · v2
theory

Abstract

Computing the top-$k$ \textit{simple} shortest paths between two vertices of a graph, i.e., solving the P-KSSP problem, is a fundamental primitive in graph analytics. In modern scenarios, however, queries are rarely one-shot: parameters change as applications adapt their information needs, and recomputing a solution from scratch at every request quickly becomes a bottleneck. We study P-KSSP in a dynamic setting, focusing on changes of the parameter $k$: given a top-$k$ solution for a pair of vertices and a new value $k'$, the goal is to compute a top-$k'$ solution reusing the previously computed paths. Our approach rests on the \textit{pseudo-tree}, a compact representation of a collection of simple $s$--$t$ paths: we show that building it from an arbitrary, unstructured solution amounts to trie construction, and give two constructions running in time linear in the size of the collection. On top of it, we design UPD, a dynamic algorithm that updates a solution upon a change of $k$; we prove its correctness, analyze its complexity, and show that it is a general, solver-agnostic scheme, which starts from the paths alone, is parametric in the routine that generates candidate paths and combinable with known preprocessing techniques, as well as with an online pruning rule that we formalize. While a worst-case update is asymptotically comparable to recomputing from scratch, an extensive experimental evaluation shows that a variant of UPD is the fastest method in the large majority of tested configurations, often by a wide margin (with speedups over recomputation that grow with $k$ and $k'$ and exceed $60\times$), yielding a practical recipe for the configuration to deploy.

Closest papers

Nearest neighbours by meaning across the whole index.

A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.70
Abstract

A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.20

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.66
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter

cs.DS cs.CC ·2026-10-15 ·Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale
similarity 0.66
Abstract

We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the objective is to decide whether $G$ admits a set of $k$ isometric paths (i.e., shortest paths between their endpoints) whose union is the entire vertex set of $G$. We show that \textsc{Isometric Path Cover} is NP-hard on graphs of pathwidth (and thus treewidth) at most 287. This is an interesting contrast with the closely related problems \textsc{Isometric Path Partition} and \textsc{Path Cover}, which are both known to be XP for treewidth, see [Chakraborty et al., WG 2026] and [Foucaud et al., TCS 2026]. On the positive side, we show, by a suitable dynamic programming scheme, that \textsc{Isometric Path Cover} admits an XP algorithm w.r.t.~the parameter combination of treewidth and diameter, running in time $n^{\diam^{O(\tw)}}$ where $\diam$, $\tw$, and $n$ denote the diameter, the treewidth, and the number of vertices of the input graph, respectively. However, we also prove that \textsc{Isometric Path Cover} becomes W[1]-hard for pathwidth on graphs of diameter~7, showing that an XP algorithm is the best one can hope for w.r.t.~this parameterization, under standard complexity theory assumptions.

0.21

Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs

cs.DS cs.DM ·2026-09-19 ·Shisheng Li
theory similarity 0.65
Abstract · 15 pages

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.

0.21

Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time

cs.DS ·2026-10-23 ·Niels Inselmann Christiansen, Eva Rotenberg
similarity 0.64
Abstract

We consider the problem of maintaining the triconnectivity in a graph $G$ in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries that take as input variables the vertices $a$ and $b$ and are of the form ''are there at least three vertex disjoint paths between $a$ and $b$?''. All algorithms presented in this paper are deterministic. When starting from a biconnected graph, all updates take worst-case $O(\log n)$ time, and all queries are answered in $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get a deterministic algorithm for general graphs with a worst-case update and query time of $O(\log^2 n)$. Both algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.

0.22

A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth

cs.DS cs.CC ·2026-09-24 ·DongYun Byun, Akira Matsubayashi
theory similarity 0.63
Abstract · 22 pages, 1 figure. Presented in IPEC 2026

The $k$ vertex-disjoint paths problem asks whether, given a graph $G$ and $k$ pairs of vertices $(s_1,t_1)$, \ldots, $(s_k,t_k)$, $G$ has $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all $1\leq i\leq k$. If $G$ is undirected, then this problem is NP-complete, but there exist FPT algorithms parameterized by $k$.Since these algorithms involve an extremely large function on $k$, algorithms for restricted graphs have also been investigated. In particular, a $2^{2tw\log tw+O(tw)}\cdot n$ time algorithm for undirected graphs with $n$ vertices and treewidth $tw$ is proposed by Scheffler (Technical Report 396, TU Berlin, '94), and it is proved by Lokshtanov, Marx, and Saurabh (SIAM J. Comput. '18) that, under the ETH, there exists no $2^{o(pw\log pw)}\cdot n^{O(1)}$ time algorithm for either directed or undirected graphs with pathwidth $pw$ and for $k=Ω(pw^4)$. It has not been known whether the lower bound also holds for a smaller $k$. In this paper, we prove that, for both the directed and undirected cases, there is an algorithm faster than Lokshtanov et al.'s lower bound for $k=tw^{o(1)}$ by proposing a $2^{O((tw+k)\log k)}\cdot n$ time algorithm. Besides, we prove a lower bound that, under the SETH, there exists no $(2-ε)^{pw\log pw}\cdot n^{O(1)}$ time algorithm for directed graphs and for a general $k$. This lower bound is tight because, with slight modifications, Scheffler's algorithm runs in $2^{pw\log pw+O(pw)}\cdot n$ time also for directed graphs.

0.26

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

cs.DS cs.CG ·2026-09-24 ·Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht
similarity 0.63
Abstract · To apear in ISAAC 2026

We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.

0.20

Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm

cs.DS ·2026-09-28 ·Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg, Antti Roeyskoe, Aurelio Sulser +1 more
similarity 0.63
Abstract

Given an undirected weighted graph $G$, a $γ$-approximate low-stretch spanning tree (LSST) $T \subseteq G$ is a tree that approximates the distance metric of $G$ up to a $γ$-factor in expectation. Currently, existing algorithms to find a provably good LSST carefully construct an approximate shortest-path tree from an arbitrary source. The resulting algorithms are intricate. In contrast, practitioners observed that a much simpler heuristic performs surprisingly well: choose an arbitrary root, run Dijkstra's algorithm, and use the resulting shortest-path tree as an LSST. In this paper, we give a smoothed analysis of shortest-path tree algorithms, such as Dijkstra's algorithm, that explains this behavior. We show that adding a small perturbation to the weights of the input graph suffices to turn the shortest path tree rooted at an arbitrary node in the resulting graph into an $\tilde{O}(1)$-approximate LSST. We further show that the set of perturbations can be computed efficiently from few low-diameter decompositions (LDDs). Thus, our proof is also constructive in the sense of giving a novel approach to computing LSSTs.

0.40