CS Paper Radar

Minimum eccentricity shortest paths of $K_{2,3}$-minor-free graphs

Dibyayan Chakraborty, Sandip Das, Sk Samim Islam, Ritam Manna Mitra, Saumya Sen

cs.DS ·submitted 2026-08-13 12:25 UTC · v1
theory

Abstract

Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists an \emph{isometric path} $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.

Comment
11 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Eccentricity Shortest Path: the structural parameter landscape

cs.DS math.CO ·2026-10-14 ·Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
theory similarity 0.72
Abstract · 74 pages, short abstract for arXiv

The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove $\mathsf{W}[3]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\mathsf{W}[2]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\ell$, we obtain an $O(\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\mathsf{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.

0.24

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.64
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

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.63
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

The Cayley Completion of a Graph

cs.DM cs.DSmath.CO ·2026-08-31 ·Rigobert Fokam Souop, Laurent Bitjoka
theory similarity 0.63
Abstract

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completion number $γ^{+}$ (additions only) and the Cayley edit distance $γ_{\triangle}$ (both), each normalized by $m$. We show that deciding the edit version is NP-complete already for a fixed cyclic host, by a reduction from Hamiltonian Cycle in which the edit cost of a labeling is $n+m-2k$ when it realizes a longest path with $k$ edges; the optimal cost is $m-n+2pp(G)$, bounded in polynomial time by the matching number. We prove that irregularity alone forces $γ^{+}(G)\ge nΔ^{*}/(2m)-1$, where $Δ^{*}$ is the least $d\geΔ$ with $nd$ even, computable in linear time from the degree sequence; we characterize equality exactly. It is attained on the star, where $γ^{+}(K_{1,q})=(q-1)/2$ and the star maximizes $γ^{+}$, while $γ_{\triangle}$ stays bounded by an absolute constant. We determine paths and grids exactly, $γ^{+}(P_n)=γ^{+}(P_n\,\square\,P_n)=1/(n-1)$, and show $γ_{\triangle}(K_{1,q})\to 2$, not the $3/2$ suggested by the additive case. We report an exhaustive certified census of all $995$ connected graphs on at most seven vertices. The degree bound is attained on $89.4\%$ and the two invariants separate strictly on $84.7\%$, though both rates vary sharply with order: attainment $100\%,100\%,84.8\%,89.7\%$ and separation $0\%,61.9\%,73.2\%,87.7\%$ for $n=4,5,6,7$, dominated by the $853$ graphs on seven vertices. The star uniquely maximizes both. Edit count and the bi-Lipschitz distortion of the completed host are independent, moving oppositely on stars and paths.Data and certificates at doi:10.5281/zenodo.21852006.

0.49

When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance

cs.DS ·2026-09-18 ·Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams
theory similarity 0.62
Abstract · 20 pages

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

0.28

A Low-Diameter Nash-Williams--Tutte Theorem

cs.DM math.COcs.DS ·2026-11-03 ·Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai, Ting-An Wu
theory similarity 0.62
Abstract

The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

0.29

A 5/4 bound for graphic $s$-$t$ path TSP on subcubic graphs

cs.DS cs.DMmath.CO ·2026-08-11 ·Junho Hwang
theory similarity 0.62
Abstract · 12 pages, 2 figures

We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given distinct vertices $s,t$, find a shortest $s$-$t$ walk that visits every vertex. We prove an upper bound with the asymptotically optimal leading coefficient $5/4$ for every terminal pair, even when $G-\{s,t\}$ is disconnected. Specifically, every simple 2-connected subcubic graph $G$ on $n$ vertices has a spanning $s$-$t$ walk of length at most $\lfloor(5n+n_2(G))/4\rfloor$, where $n_2(G)$ counts its degree-2 vertices. An $O(n^2)$-time algorithm attains this bound. Combining an edge-rooted even-cover theorem of Wigal, Yoo, and Yu (WYY) with an even-cover-to-walk lemma proved here yields this bound for adjacent terminals, a consequence not stated explicitly in their paper. We extend the bound to arbitrary terminal pairs. For cubic graphs, it becomes $\lfloor 5n/4 \rfloor$, to our knowledge the first direct $5/4$ bound for cubic path TSP that does not use the general path-to-tour reduction.

0.10

Simple analysis of an algorithm for multiple-source shortest paths in planar graphs

cs.DS ·2026-10-01 ·Philip N. Klein
similarity 0.62
Abstract

This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein gave an $O(n \log n)$ algorithm for this problem; the algorithm subsequently became an essential ingredient in dozens of algorithms, addressing problems ranging from distance oracles to edit distance. However, the correctness and analysis in that original paper is complicated and messy and hard to understand. In this paper, we give a simple and clear analysis.

0.25