CS Paper Radar

Tolerant Testers for Subgraph-Freeness

Reut Levi, Jonathan Meiri

cs.DS ·submitted 2026-10-14 18:59 UTC · v1
published

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

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-09-30 ·Pan Peng, Kefan Yu
theory similarity 0.77
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

Near-Linear Lower Bounds for Testing Directed Acyclicity

cs.DS ·2026-11-03 ·Artur Czumaj, Pan Peng, Yuyang Wang
similarity 0.70
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

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

Testing Connectedness and Edge Connectedness

cs.DS ·2026-10-15 ·Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
theoryhot direction similarity 0.68
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.

0.28

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.68
Abstract

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

0.55

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

cs.DS ·2026-11-16 ·Marin Bougeret, Juan Pablo Bravo, Daniel Gonçalves
theory similarity 0.67
Abstract · 43 pages, 8 figures, submitted

A number of recent works have investigated the existence of parameterized subexponential algorithms in geometric graph classes for hitting a fixed small graph as a subgraph or as a minor. In this setting, given an $n$-vertex graph, the goal is to decide in time $n^{O(1)}2^{o(k)}$ if a solution of size at most $k$ exists. Inspired by recent results in kernelization for structural parameters, we investigate subexponential algorithms for the Vertex Cover (VC) problem, but parameterized by distance-to-triviality instead of solution size. More formally, given a fixed "trivial" graph class $\mathcal{C}$, the problem takes as input $(G,X,k)$, where $G \setminus X \in \mathcal{C}$, and asks if $G$ admits a vertex cover of size at most $k$. Our goal is to design algorithms for this problem running in time $n^{O(1)}2^{o(|X|)}$. The motivation is that, since $|X|$ is typically arbitrarily smaller than $k$, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by $k$. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where $\mathcal{C}$ is the class of paths, and another for the case where $\mathcal{C}$ is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that $s$-string graphs and pseudo-disk graphs satisfy the first set of conditions, whereas string graphs satisfy the second set. The two sets share a common condition that might be of independent interest, as it implies a property that bounds the treewidth of any string graph in terms of a given modulator to a fixed graph class $\mathcal{C}$. Finally, concerning more restricted graph classes having the $ASQGM(ω)$ property (such as map graphs and $H$-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in $\mathcal{C}$.

0.14

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.66
Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

0.20

An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem

cs.DS cs.DM ·2026-09-20 ·Min Chih Lin, Natán Vekselman
similarity 0.66
Abstract · 10 pages. Expanded implementation details and complexity justification; clarified the word-RAM model, clique-event processing, and the discu…

For a fixed integer $r\geq4$, the $K_r-e$-free graph sandwich problem asks whether, given graphs $G_1\subseteq G_2$ on the same vertex set, there is an induced-$K_r-e$-free graph $H$ between them. We give a deterministic algorithm taking $O(n+α(G_2)^{r-3}m_2)$ time and space, where $m_2=|E(G_2)|$ and $α(G_2)$ is the arboricity of $G_2$. In particular, the diamond-free case takes $O(n+α(G_2)m_2)$ time. This improves the direct $O(n^r m_2)$ implementation of the previously known forced-edge closure. Our implementation maintains components of common neighborhoods indexed by $(r-3)$-cliques. A filtered frontier supports their merges within the clique-listing bound, while completion events avoid repeatedly searching for affected cliques. On feasible instances the output is contained in every feasible sandwich, independently of processing order. Applying the closure to $(G,K_n)$ gives an $O(n^{r-1})$-time bound for partitioned and nonpartitioned probe $K_r-e$-free recognition, improving the $O(n^{r+2})$ bound obtained from the direct sandwich closure. We also describe a direct static recognizer based on the same local characterization.

0.18