CS Paper Radar

Testing Connectedness and Edge Connectedness

Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

cs.DS ·submitted 2026-10-15 05:45 UTC · v1
theoryhot direction

Abstract

We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that $\varepsilon$-testing connectedness of graphs with maximum degree at most $d$ requires $Ω(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon d})$ queries (when $\varepsilon \le \frac{1}{4d^5}$). Our result implies that the connectedness tester of Levi, Pallavoor, Raskhodnikova, and Varma ({\em ACM Trans.\ Comput.\ Theory, 2022}) is optimal. We also study the problem of testing $k$-edge-connectedness of both directed and undirected graphs of average degree $\overline{d}$ in the adjacency lists model and design a tester with query complexity $O(\frac{k}{\varepsilon} \log \frac{1}{\varepsilon \overline{d}})$, improving upon the bounds by Forster, Nanongkai, Saranurak, Yang, and Yingchareonthawornchai (SODA 2020). Furthermore, we complement our upper bound by showing that every one-sided error $k$-edge-connectedness tester must make $Ω(k/\varepsilon)$ queries.

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Linear Lower Bounds for Testing Directed Acyclicity

cs.DS ·2026-11-03 ·Artur Czumaj, Pan Peng, Yuyang Wang
similarity 0.73
Abstract

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

0.24

Tolerant Testers for Subgraph-Freeness

cs.DS ·2026-10-14 ·Reut Levi, Jonathan Meiri
published similarity 0.68
Abstract

In this paper we study the problem of tolerantly testing the property of being $H$-free (which also implies distance approximation from being $H$-free). In the general-graphs model, we show that tolerant $K_k$-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph $G$, $arb(G)$, and independent of the size of $G$ (for graphs in which the average degree is $Ω(1))$. Specifically for triangles, our algorithm distinguishes graphs which are $ε$-close to being triangle-free from graphs that are $3ε(1+η)$-far from being triangle-free with expected query complexity which is $\tilde{O}(arb^3(G))$ (for constant $η$ and $ε$). For general $k$-cliques our algorithm distinguishes graphs which are $ε$-close to being $K_k$-free from graphs which are ${k \choose 2}ε(1+η)$-far from being $K_k$-free with expected query complexity which is polynomial in $k$, $1/ε$, $1/η$ and $arb(G)$. We then generalize our result and provide a similar result for any motif $H$ which is $2$-connected and has radius $1$. This includes for example the wheel graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing $H$-freeness for any motif $H$. The query complexity of the algorithm is polynomial in the degree bound, $d$, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in $d$.

0.32

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

cs.DS ·2026-09-30 ·Pan Peng, Kefan Yu
theory similarity 0.68
Abstract

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.

0.16

Testing MAX-CUT in the Adjacency Matrix Model: Tight Non-Adaptive Bounds and a Cubic Adaptive Lower Bound

cs.DS ·2026-10-31 ·Songhua He
theory similarity 0.67
Abstract

We study the query complexity of approximating the MAX-CUT value to additive error $\varepsilon n^2$ in the adjacency matrix model. This was one of the first problems studied in graph property testing [GGR'98]. Previously, the best known upper bound for both adaptive and non-adaptive algorithms was $O(1/\varepsilon^6)$ [RV'07; MS'08; GMRS'22]. The only known lower bound was a trivial $Ω(1/\varepsilon^2)$ bound. We close this gap from both sides for non-adaptive algorithms, proving that its query complexity is exactly $Θ(1/\varepsilon^4)$. We also prove an adaptive $Ω(1/\varepsilon^3)$ lower bound. Our upper bound is achieved by a canonical tester that samples $O(1/\varepsilon^2)$ vertices in expectation and outputs the rescaled MAX-CUT value of the induced subgraph. We prove its correctness by applying spectral truncation to the adjacency matrix, using a geometric argument to control the sampling error of the retained low-rank part and a cut-norm restriction estimate [RV'07] for the remainder. As an application, an analogous proof also yields a tight $O(1/\varepsilon^4)$ non-adaptive query upper bound for MAX-2CSP. For our lower bounds, we show indistinguishability between a uniform random graph and a random graph with a planted hidden partition. For the non-adaptive lower bound, we observe that one plus the $χ^2$-divergence between the query transcript distributions is exactly a normalized Ising partition function, which can be bounded using Boolean hypercontractivity. For the adaptive lower bound, we relate each query's distinguishing power to the prediction, based on previous answers, of whether its endpoints lie in the same part of the hidden partition. We bound the combined advantage of these predictions using the completed transcript, which lets us analyze the adaptively chosen pairs of vertices together despite their dependence on earlier answers.

0.20

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

cs.LG stat.ML ·2026-09-27 ·Soham Dan
theory similarity 0.64
Abstract

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

0.18

On (Directed) Width-Parameters of Geometric Spanners

cs.CG ·2026-09-18 ·Kevin Buchin, Carolin Rehs, Torben Scheele
published similarity 0.63
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

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.63
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

Connectivity in a New Bounded-Space Dynamic Model

cs.DS ·2026-11-05 ·Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams
theory similarity 0.63
Abstract · Submitted to STOC; shortened abstract to fit arxiv requirements

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.

0.26