CS Paper Radar

Almost Linear 3-Spanners of Temporal Cliques

Julia Baligacs, Davide Bilò, Václav Blažej, Maël Dumas, Anna Zych-Pawlewicz

cs.DS cs.DMmath.CO ·submitted 2026-09-02 17:36 UTC · v1
theory

Abstract

Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $α$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $α$. While general temporal graphs may not admit sparse temporal $α$-spanners for any value of $α$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $Ω(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams

cs.DS ·2026-10-08 ·George Manoussakis
theory similarity 0.73
Abstract

A link stream is a set of interactions between pairs of vertices, each one lasting during some time interval, and a clique of a link stream is a set of vertices together with a time interval during which all of them interact. A clique is maximal if neither its vertex set nor its interval can be enlarged. All known algorithms listing the maximal cliques of a link stream may spend time exponential in the size of a clique for each clique they output. Here, we approach the question under the light of two parameters of the instantaneous graphs of the stream, their maximum degree $Δ$ and their degeneracy $k$. We prove that a link stream with $m$ links has $O(mΔ^2 3^{Δ/3})$ maximal cliques, and that a link stream with $n$ vertices and $|\mathcal{T}|$ distinct end times has $O(n|\mathcal{T}|k^2 3^{k/3})$ maximal cliques. Both bounds are tight up to a factor polynomial in $Δ$ and $k$ respectively, and the second one improves the factor $2^k$ of previous bounds to $3^{k/3}$. Then we present two algorithms. The first one has setup time $O(m\log m)$ and polynomial time delay $\mathrm{poly}(Δ)\log m$. The second one has setup time $O(m\log m+mk^2\log^3 n)$ and polynomial time delay $\mathrm{poly}(k)\log m$. To the best of our knowledge, these are the first algorithms with polynomial time delay for this problem. We also give an online version of the second algorithm, and we show that our results apply to the $Δ$-cliques and $(Δ,γ)$-cliques of temporal graphs.

0.42

Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs

cs.DS cs.DM ·2026-10-05 ·Daniele Carnevale
theory similarity 0.72
Abstract · 21 pages, 2 figures

A temporal graph is a sequence of graphs on a common set of $n$ vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time step wait or move along an edge of the current snapshot, and the temporal graph is explored once the agent has visited every vertex. We consider always-connected temporal graphs, in which every snapshot is connected, and ask how long exploration can be forced to take when the underlying graph, the union of all snapshots, has maximum degree at most~$Δ$. Two lower bounds were known in this setting, $Ω(Δn)$ and $Ω(n\log n)$, realised by different constructions. We establish a stronger lower bound, answering a question of Bastide, Groenland, Michel and Rambaud. Specifically, for every $n$ and $Δ$ with $Δ_0\leΔ\le n-1$ we construct an always-connected temporal graph on $n$ vertices with underlying maximum degree at most~$Δ$ that cannot be explored in fewer than $γ\,Δn\,(1+\log(n/Δ))$ time steps from any start vertex, where $γ>0$ and $Δ_0$ are absolute constants. The construction is deterministic, and every snapshot is a spanning tree with exactly one vertex of degree greater than three. Time is divided into phases. In each phase, a rotating-cycle gadget prevents the agent from reaching more than half of the trees attached to it. Between phases, we reassign target vertices among these trees using walks on a constant-degree expander, and a Gray code order of the targets keeps the underlying degree bounded. The reassignment guarantees that, for any walk of the agent, some target remains unvisited throughout all phases.

0.41

Recognizing Label-Connected Graphs

cs.DS cs.DM ·2026-11-03 ·Ralf Klasing, George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
similarity 0.69
Abstract

In classical gossiping, each participant initially knows a distinct piece of information. Whenever two participants call each other, they exchange everything they know. We study Gossiping: given an undirected multigraph whose vertices represent participants and whose edges represent available calls, decide whether the calls can be ordered so that every participant learns all information, using each edge at most once. Equivalently, can one time label per edge make the graph temporally connected by strict temporal paths? This recognition problem is NP-complete; we study its parameterized complexity. After linear-time preprocessing, we give an exact $O(3^{n/3}n^3)$-time algorithm and a deterministic $2^{O(tw)}n$-time algorithm, where $n$ is the number of vertices and $tw$ is the treewidth of the underlying simple graph. We introduce a Tree Contraction Rule that extends the treewidth algorithm to single-exponential algorithms for parameters that may remain small on dense graphs, such as tree-independence number and clique-width, without requiring a decomposition as input. For the excess $δ=m-(2n-4)$ over the minimum number of calls, where $m$ is the number of edges, we give a randomized $2^{O(δ)}n^3$-time algorithm with one-sided error. Its main subroutine solves Rooted Independent Cycle: finding a cycle through four prescribed vertices whose edges are independent in a represented linear matroid. We solve this problem deterministically in $2^{O(r)}m$ arithmetic operations over the finite field representing the matroid, where $r$ is its rank. Gossiping is polynomial-time solvable at maximum degree four, counting parallel edges, but NP-complete on planar simple graphs of maximum degree five. The treewidth algorithm yields a $2^{O(\sqrt n)}$-time algorithm on planar graphs.

0.29

$(α, β)$ Spanners and Hybrid Spanners with Nearly Tight Bounds

cs.DS cs.DM ·2026-09-30 ·Shiri Chechik, Gur Lifshitz
top venue similarity 0.69
Abstract · A preliminary version appeared in SODA 2026

For an $n$-vertex undirected, unweighted graph $G=(V,E)$ and a positive integer $k$, we present new spanner constructions with $O_k(n^{1+1/k})$ edges that achieve nearly optimal guarantees for all distances $d\le k$. Specifically, we construct a spanner $H\subseteq G$ with $O(n^{1+1/k}+(k+d\log d)n)$ edges, ensuring that any pair at original distance at most $d$ satisfies $\mathrm{dist}_H(u,v)\le 2k+O(d\log d)$. Equivalently, the multiplicative stretch for pairs at distance $d$ is $2k/d+O(\log d)$. In particular, setting $d=k/\log k$ yields an $(O(\log k),O(k))$-spanner with $O(n^{1+1/k}+kn)$ edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed $\varepsilon>0$ and sufficiently large $k$, an $(O(k^\varepsilon),O_\varepsilon(k))$-spanner with $O_{\varepsilon,k}(n^{1+1/k})$ edges. Our result improves the multiplicative stretch from $O(k^\varepsilon)$ to $O(\log k)$ while keeping the additive term linear in $k$, bringing us closer to the goal of $(O(1),O(k))$-spanners. Furthermore, Ben-Levy and Parter obtained multiplicative stretch $O_\varepsilon(k/d)$ for distances $d\le k^{1-\varepsilon}$, for every fixed $\varepsilon>0$, and an explicit bound of $7k/d$ for $d\le\sqrt{k}/2$. We achieve $2k/d+O(\log d)$, which is $(2+o(1))k/d$ whenever $d=o(k/\log k)$. Our second result is an improved construction of $k$-hybrid spanners, which guarantee stretch $2k-1$ for adjacent pairs and $k$ for non-adjacent pairs. Parter's original construction uses $O(k^2 n^{1+1/k})$ edges; we achieve the same guarantees with $O(n^{1+1/k}+kn)$ edges, removing the $k^2$ factor from the $n^{1+1/k}$ term. For every fixed $k$, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.

0.49

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.67
Abstract · Accepted at ISAAC 2026

To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) $t$-spanner $G$ for a point set $P$ in the Euclidean space is a (directed) graph such that for every pair of points, the shortest path in $G$ is at most a factor $t$ longer than the Euclidean distance between those points. In this paper, we investigate $t$-spanners that are bounded by certain graph parameters. Let $κ$ be a graph parameter. We show that for path-width, branch-width and cut-width there is an $\mathcal{O}(n/k^{d/(d-1)})$-spanner $G$ on $P$ with $κ(G)=k$ and that this is asymptotically worst-case optimal. In $\mathbb{R}^2$ we show the same bounds for planar graphs of clique-width or rank-width $k$. In contrast, for tree-depth, we show that there are sets of points for which the dilation cannot be bounded. Therefore, we investigate computing a spanner with tree-depth $k$ and minimum dilation. We show that already for tree-depth $3$ this problem is NP-hard to approximate within any factor strictly less than $\sqrt{2}$, and present an XP-algorithm to compute for a given tree-depth $k$ a graph with dilation at most $2t^*$, where $t^*$ is the minimum dilation. We further extend these results to obtain directed $\mathcal{O}(n/k^{d/(d-1)})$-spanners $G$ with $κ(G)=k$ for $κ$ being directed tree-width, directed path-width or DAG-width and show that also in the directed case, this is asymptotically worst-case optimal.

0.29

Enumerating Small Potential Maximal Cliques with Fixed-Parameter Delay

cs.DS cs.DB ·2026-10-17 ·Batya Kenig
similarity 0.67
Abstract

A potential maximal clique (PMC) of a graph $G$ is a nonempty vertex set that forms a maximal clique in some minimal triangulation of $G$. Listing the PMCs of a graph is a key step in exact algorithms for computing treewidth, minimum fill-in, and related graph parameters. We present a deterministic algorithm that enumerates all PMCs of cardinality at most $k$ in an $n$-vertex graph $G$, without repetition, with delay $2^{O(k^3)}n^4\log n$. This bound also covers the preprocessing time before the first output, the time from the last output to termination, and the total running time when no such PMC exists. At the core of our enumeration algorithm is a procedure that solves the following constrained search problem within the same time bound: given sets of required and excluded vertices $I,O\subseteq V(G)$, find a PMC $Ω$ of size at most $k$ satisfying $I\subseteqΩ$ and $Ω\cap O=\emptyset$, or determine that none exists. Our enumeration algorithm directly supports these inclusion and exclusion constraints as well. Our approach builds on the \emph{recursive understanding} technique of Chitnis et al.~\cite{chitnis2016} and the reduction to unbreakable graphs of Lokshtanov et al.~\cite{lokshtanov2018}. A graph is $(q,k)$-unbreakable if no removal of at most $k$ vertices leaves two disjoint unions of connected components that each contain more than $q$ vertices. We first solve constrained PMC search on $(q,k)$-unbreakable graphs, and then apply this procedure to replace separated subgraphs with graphs of size $2^{O(k^2)}$ that preserve the existence of a constrained solution for every graph attached along the shared boundary.

0.21

Improved polynomial-time algorithms for detecting and recovering planted $Θ(\sqrt{n})$-cliques

cs.DS math.ST ·2026-09-21 ·Dmitriy Kunisky, Songtao Mao
similarity 0.66
Abstract · 77 pages

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected graphs of treewidth at most $t$, cliques of size $k = λ\sqrt{n}$ planted in a random location with $λ> 1 / \sqrt{c(t)}$ can be detected and recovered in time $n^{t + 1 + o(1)}$. For instance, since $c(1) = e$, this recovers by counting signed trees the performance of the $\widetilde{O}(n^2)$-time message-passing algorithm of Deshpande--Montanari (2015) that succeeds when $λ> 1 / \sqrt{e} \approx 0.6066$. For $t \geq 3$, the exact value of $c(t)$ is not known, but lower bounds on it give a hierarchy of slower polynomial-time algorithms that succeed for smaller $λ$. We further show that the above algorithm for $t = 2$ can be implemented in time $n^{ω+ o(1)}$ for $ω$ the constant of square matrix multiplication and succeeds when $λ> 0.3320$; under the folklore conjecture that $ω= 2$, this runs in the nearly-linear time of the algorithm of Deshpande--Montanari while finding smaller cliques. Second, we show that the above algorithm for $t = 1$ can be combined with the boosting scheme of Alon--Krivelevich--Sudakov (1998) using rectangular matrix multiplication, giving improved runtimes for smaller $λ$. Taken together, our results achieve the best known tradeoff between runtime and signal strength $λ$.

0.27

The directed temporal exploration problem

cs.DS math.CO ·2026-09-28 ·Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang, Hehui Wu
theory similarity 0.66
Abstract

We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of $O(n^2)$ suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a $Ω(n^2)$ lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for guaranteeing the existence of a temporal exploration on temporal digraphs where each snapshot is semicomplete. For always-strong temporal digraphs where each snapshot has minimum undirected degree at least $n - c - 1$, we prove that a lifetime of $O(cn)$ guarantees the existence of a temporal exploration, and we also prove that this is asymptotically tight. From a computational perspective, our results for temporal semicomplete digraphs also yield a polynomial-time, factor-$4/3$ algorithm for deciding if a temporal semicomplete digraph admits a temporal exploration within the first $\ell$ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - ε)$ approximation algorithm exists, even if every snapshot is a tournament, unless P$=$NP.

0.14