CS Paper Radar

Tunnels: Compressing the Solution Subgraph of Regular Path Queries

Adrián Gómez-Brandón, Gonzalo Navarro

cs.DS ·submitted 2026-11-07 13:46 UTC · v1

Abstract

Regular path queries (RPQs) are increasingly expected to return the paths that match them, not only their endpoints. Since the number of matching paths can be exponential or infinite, a standard way to deliver them (PMR) is the subgraph $\Hs$ of the product between the graph and the query automaton that contains exactly the nodes lying on some solution path. We show that $\Hs$ can be compressed much further when the graph is available to the decoder: most of $\Hs$ can be regenerated by re-running small parts of the traversal, and only the places where the traversal would waste significant effort on dead branches need to be stored. We formalize this as \emph{tunnels}: regions of $\Hs$ that are re-expanded from a stored entry point with a bounded amount of extra work, either an absolute budget or one proportional to the output produced. We handle the three classes of RPQs: constant-to-variable, constant-to-constant, and variable-to-variable. In the latter, we study the combination of tunnels with cutting the query at a selective articulation point of the automaton and encoding the answer as a union of Cartesian products of leftward and rightward traversals. Our experimental results show improvements of 2 to 3 orders of magnitude over the baseline space of PMR, for an acceptable increase in traversal time.

Closest papers

Nearest neighbours by meaning across the whole index.

Towards Dynamic Top-$k$ Simple Shortest Paths

cs.DS ·2026-10-14 ·Gianlorenzo D'Angelo, Andrea D'Ascenzo, Mattia D'Emidio, Gabriele Di Stefano, Marta Innamorati
theory similarity 0.60
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.

0.30

Searching subgraphs

cs.DS ·2026-10-18 ·Dariusz Dereniowski, Boting Yang
hot direction similarity 0.60
Abstract

We consider graph search models, in which an invisible, omniscient and fast intruder can hide anywhere in the graph, and the goal is to design a \emph{search strategy} composed of a sequence of movements of \emph{searchers} that guarantees the capture of the intruder regardless of its actions. Our point of departure is the connected search model in which the cleared subgraph is always connected during the search process. In this paper, we initiate the study of the subgraph searching problems which arise from the following question: what happens if the number of searchers available is not sufficient to clear a given graph $G$? We propose an approach in which one wants to clear in a connected way as large subgraph as possible with the given $k$ searchers. In this context we study two problems: one problem, called the \emph{subgraph search}, is to find the maximum-sized subgraph whose search number is at most $k$, and the other one, called the \emph{protected subgraph search}, is to perform a partial search on $G$ leading to as many cleared edges as possible. Informally speaking, the difference lies in the fact that in the latter a recontamination may come from an edge never to be cleared and hence the partial search strategy needs to avoid such recontaminations. Having proved that both problems are computationally hard in general, we give efficient algorithms for $n$-vertex trees: an $\bigo(\min\{kn, n \log n\})$ time algorithm for the subgraph search and an $\bigo(\min\{2^{6k}kn, n^{8.571} \log n\})$ time algorithm for the protected subgraph search.

0.32

Hardness of Pathfinding in a Welded Tree

cs.CC quant-ph ·2026-09-17 ·David Miloschewsky, Supartha Podder
theory similarity 0.60
Abstract · 55 pages, 4 figures

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

0.29

A Simple Subquadratic Cut Query Protocol for Directed Reachability

cs.DS ·2026-11-04 ·Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
similarity 0.59
Abstract · 17 + 22 pages

We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.

0.54

Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity

cs.LG ·2026-08-12 ·Debanjan Dutta, Anish Chakrabarty, Swagatam Das
similarity 0.58
Abstract

Chain of Thought (CoT) lifts the expressive ceiling of bounded-depth Transformers, with characterizations tying the number of CoT steps to circuit complexity classes. What remains largely missing are concrete instantiations with explicit, depth-bounded constructions, and the traversal procedures such characterizations presuppose. We close this gap for branching complexity. We give CoT realizations of depth-first search (DFS) and of Dijkstra algorithm, the latter subsuming breadth-first search, by unique hard-attention decoders of at most two layers, and use them as a shared computational substrate: reusing the DFS decoder yields the Strahler number of an $n$-vertex tree in $2n-1$ steps with four layers, and reusing the Dijkstra decoder yields its width in $n-1$ steps with three. Since computing the Strahler number of a binary tree given as a term is \textsf{NC\textsuperscript{1}}-complete, and our constructions handle arbitrary $n$-ary trees without layer normalization or positional encodings, this is a non-trivial witness for the linear-step regime of the CoT hierarchy. Exploiting the classical bijection between ordered trees and Dyck paths, itself realized by our DFS construction, which emits the path as it traverses, we give independent constructions for both measures on the path representation.

0.04

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.58
Abstract · SODA 2027

We present a significantly improved $k$-fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph $G$ that, given any set $F$ of failed edges of size $|F|\le k$, answers whether $G \setminus F$ is strongly connected. For every constant $k$, our oracle only uses $n^{1+o(1)}$ space and $n^{o(1)}$ query time. No prior result can achieve $o(n^{2})$ space and $o(n)$ query time, \emph{even when $k=2$}. Previous oracles either require $Ω(n)$ query time [BCR18], or $Ω(n^2)$ space [vdBS19]. Our main technical contribution is a \emph{rooted} version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph $G$, an integer $k$, and a source vertex $s$, we can sample a set of edges $A$ such that each minimal $s$-rooted cut of size at most $k$ becomes an $s$-rooted min-cut in $G + A$ with probability $2^{-poly(k)}n^{-o(1)}$.

0.57

Dense Interprocedural Dominance in Acyclic Graphs: Context Bounds and Compact Queries

cs.DS ·2026-09-05 ·Peisen Yao
similarity 0.58
Abstract · We identified a substantive technical issue in the proof of the main theorem that affects several downstream results. Addressing the issue r…

Interprocedural dominance asks which program points every matched call-and-return execution must pass on its way to a target. An analysis that writes out immediate dominance pays for the transitive reduction of this order, the minimal dominator graph. Measured instances of that graph look near-linear, with edge-to-node ratios around 1.1--1.26~\cite{DeSutter2007}, but no program property is known to force this: it is unclear which structural restrictions imply sparse output, and whether dense output also rules out cheap queries. This paper answers both through calling contexts. A static node stands for the group of its reachable configurations; write $κ$ for the largest group size and $α$ for how many nodes have more than one configuration. One context per node keeps the tree with $n-1$ edges. Two already allow $Θ(n^2)$ cover edges in a sparse, loop-free, recursion-free ICFG with total degree three, constant-size procedures, and logarithmic stack depth, while the reachable configuration graph itself stays linear, so the blowup comes from grouping, not from many configurations. Three keep $Θ(n^2)$ covers even when the explicit call/return graph is acyclic: all target-reaching runs visit the mandatory procedures in the same order, and extra runs that stop short of any target remove the comparabilities that would otherwise kill the covers. Complementing the lower bounds, $α$ ambiguous nodes admit at most $\min\{\floor{n^2/4},(α+1)(n-1)\}$ cover edges, with $Ω(αn)$ attainable at stack depth one. And for every ICFG with at most two contexts per node, deleting a context group reduces dominance to dual-failure reachability, giving $O(n)$-word, $O(1)$-query representation after polynomial preprocessing. Explicit cover size, context ambiguity, and query-space cost are three separate quantities.

0.26

Smallest Cubic Non-1-Planar Graphs

cs.CG math.COcs.DM ·2026-09-23 ·Sergey Pupyrev
similarity 0.57
Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

0.28