New Oracles and Labeling Schemes for Vertex Cut Queries Yonggang Jiang, Merav Parter, Asaf Petruschka Abstract We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected n n -vertex graph G = ( V , E ) G=(V,E) and integer parameter f ≥ 1 f\geq 1 , the goal is supporting vertex cut queries: Given F ⊆ V F\subseteq V with | F | ≤ f |F|\leq f , determine if F F is a vertex cut in G G . In the centralized data structure setting, it is required to preprocess G G into an f f -vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in G G , so that a cut query F F can be answered by merely inspecting the labels assigned to the vertices in F F . While the “ s ​ t st cut variants” of the above problems have been extensively studied and are known to admit very efficient solutions, the basic (global) “cut query” setting is essentially open (particularly for f > 3 f>3 ). This work achieves the first significant progress on these problems: • f f -Vertex Cut Labels: Every n n -vertex graph admits an f f -vertex cut labeling scheme, where the labels have length of O ~ ​ ( n 1 − 1 / f ) \tilde{O}(n^{1-1/f}) bits (when f f is polylogarithmic in n n ). This nearly matches the recent lower bound given by Long, Pettie and Saranurak (SODA 2025). • f f -Vertex Cut Oracles: For f = O ⁡ ( log ⁡ n ) f=O(\log n) , every n n -vertex graph G G admits f f -vertex cut oracle with O ~ ​ ( n ) \tilde{O}(n) space and O ~ ​ ( 2 f ) \tilde{O}(2^{f}) query time. We also show that our f f -vertex cut oracles for every 1 ≤ f ≤ n 1\leq f\leq n are optimal up to n o ⁡ ( 1 ) n^{o(1)} factors (conditioned on plausible fine-grained complexity conjectures). If G G is f f -connected, i.e., when one is interested in minimum vertex cut queries, the query time improves to O ~ ​ ( f 2 ) \tilde{O}(f^{2}) , for any 1 ≤ f ≤ n 1\leq f\leq n . Our f f -vertex cut oracles are based on a special form of hierarchical expander decomposition that satisfies some “cut respecting” properties. Informally, we show that any n n -vertex graph G G can be decomposed into terminal vertex expander graphs that “capture” all cuts of size at most f f in G G . The total number of vertices in this graph collection is O ~ ​ ( n ) \tilde{O}(n) . We are hopeful that this decomposition will have further applications (e.g., to the dynamic setting). 1 Introduction The study of vertex cuts in graphs has a long and rich history, dating back to works by Menger (1927, [ Men27 ] ) and Whitney (1932, [ Whi32 ] ). In recent years, substantial progress has been made in understanding vertex cuts from computational standpoints (see e.g., [ CGK14 , NSY19 , LNP+21 , SY22 , PSY22 , HLSW23 , JM23 , BJMY25 , JNSY25 ] and references therein), helping to bridge long-standing gaps with edge cuts. A vast majority of this work has been focused on computing the vertex connectivity, i.e., the minimum size of a vertex cut. Despite exciting advancements, (global) vertex cuts continue to pose intriguing open algorithmic challenges, being a topic of significant interest and activity. In this paper, we study vertex cuts from a data structures perspective, examining centralized oracles and distributed labeling schemes ; both these data structures fit the following description: Problem 1.1 ( f -Vertex Cut Data Structure) . Given an undirected graph G=(V,E) and integer parameter f\geq 1 , the goal is to preprocess it into a data structure that answers “is-it-a-cut” queries: on query F\subseteq V s.t. |F|\leq f , decide if F is a vertex cut in G (i.e., if G-F is disconnected). In the centralized oracle setting, we measure the space , query time and preprocessing time complexities. In the labeling scheme setting, the preprocessing should produce a succinct label L(v) for every vertex v\in V , and the query algorithm is restricted to merely using the information stored in the labels of the query vertices F . The most important complexity measure is the (maximum) label length \max_{v\in V}|L(v)| , where |L(v)| denotes the bit-length of L(v) . The “ st variants” of the above data structures, commonly referred to as f - vertex failure connectivity oracles/labels , have been introduced by Duan and Pettie [ DP10 ] and extensively studied in recent years [ DP20 , HN16 , vdBS19 , PSS+22 , Kos23 , HKP24 , LW24 , PP22 , PPP24 , LPS25 ] . In the st variant, the query consists of F along with two vertices s,t\in V , and should determine if s,t are connected in G-F . (This is sometimes split further into an update phase where only F is revealed, followed by connectivity queries in G-F of different vertex pairs s,t .) The current state-of-the-art oracles have converged into deterministic O(m)+(fn)^{1+o(1)}+\tilde{O}(f^{2}n) preprocessing time, \widetilde{O}(fn) space, \widetilde{O}(f^{2}) update time and \widetilde{O}(f) query time, by Long and Wang [ LW24 ] . 1 1 1 Throughout, the \tilde{O}(\cdot) notation hides \operatorname{poly}\log n factors. All these complexities are almost optimal due to (conditional) lower bounds by Long and Saranurak [ LS22a ] . As for labels, the current record is label length of \tilde{O}(f^{2}) bits (randomized) or \tilde{O}(f^{4}) bits (deterministic) by Long, Pettie and Saranurak [ LPS25 ] , where the known lower bound is \Omega(f+\log n) [ PPP24 ] . However, much less is known on global vertex cut data structures. To this date, efficient f -vertex cut oracles are known only for f\leq 3 [ BT89 , CBKT93 ] . Pettie and Yin [ PY21 ] posed the question of designing efficient f -vertex cut oracles for any f , even under the simplified assumption that the given graph is f -vertex connected. Long and Saranurak [ LS22a ] have shown that rather surprisingly, global f -vertex cut oracles must have much higher complexities then their st variants: even when f=n^{o(1)} , the query time is at least n^{1-o(1)} (with \operatorname{poly}(n) preprocessing time). Such phenomena appear also with labeling schemes: Parter, Petruschka and Pettie [ PPP24 ] posed the question of designing global vertex cut labels and showed their length must be at least exponential in f , later strengthened to \Omega(n^{1-1/f}/f) in [ LPS25 ] . Providing non-trivial upper bounds for vertex cut labels is open for any f\geq 2 . Our Contribution. This work provides the first significant progress on global f -vertex cut data structures ( Problem 1.1 ), both centralized oracles and labeling schemes, obtaining almost-optimal bounds (possibly conditional on popular conjectures). In light of the above-mentioned progress on the st -cut variants, our data structures are all generally based on reducing a single global cut query into a bounded number of st -cut queries. This strategy is inspired by the recent exciting line of works and breakthrough results in the computational setting, that are all based on this global to st reduction scheme. A prominent example is the randomized algorithm by Li et al. [ LNP+21 ] for computing (global) vertex connectivity in polylogarithmic max-flows; some other instances are [ CLN+21 , NSY23 , HHS24 ] . We now turn to discuss our results in depth. Minimum Vertex Cut Oracles. We address the open problem posed by Pettie and Yin [ PY21 ] of answering queries of the following form: Is F a minimum vertex cut in G ? This can be viewed as a f -vertex cut oracles for f -vertex connected graphs. We show: Theorem 1.1 (Minimum Vertex Cut Oracles) . Let G=(V,E) be a graph with n vertices and m edges. Let f\geq 1 be such that G is f -vertex connected. Then, there is a deterministic minimum vertex cut oracles for G with: • \tilde{O}(fn) space, • \tilde{O}(f^{2}) query time, and • O(m)+\tilde{O}(f^{2}n)+\tilde{O}((fn)^{1+\delta}) preprocessing time (for any constant \delta>0 ). The last term in the preprocessing time can be further improved to fn^{1+o(1)} , at the cost of increasing the space and query time by n^{o(1)} factors. Our space bound improves over the O(f^{2}n\log n) bound obtained by the subsequent work of [ Kos25 ] . In fact, by Theorem 1.3 which is discussed later, the space bound is optimal up to polylogartimic factors, irrespectively of query or preprocessing time. Our query time also improves over the O(f^{4}\log n) bound of [ Kos25 ] . We note that O(f^{2}) is a natural barrier for our approach, which reduces a (global) cut query F into a bounded number of st -connectivity queries in G-F . In the latter setting, this query (or more precisely, update) time is known to be conditionally tight [ LS22a ] (i.e., already for a single st -cut query); thus, an improvement seems to call for an entirely different approach. General Vertex Cut Oracles. Next, we address the problem of oracles that answer general f -vertex cut queries, where the graph is not necessarily f -connected. We show: Theorem 1.2 ( f -Vertex Cut Oracles) . Let G=(V,E) be a graph with n vertices and m edges. Let f=O(\log n) be a nonnegative integer. There is a deterministic f -vertex cut oracle for G with: • \tilde{O}(n) space, • \tilde{O}(2^{|F|}) query time (where F\subseteq V s.t. |F|\leq f is the given query), and • O(m)+\tilde{O}(n^{1+\delta}) preprocessing time (for any constant \delta>0 ). 2 2 2 Decreasing \delta leads to larger \operatorname{poly}\log n factors hidden in the \tilde{O}(\cdot) notations. The last term in the preprocessing time can be further improved to n^{1+o(1)} , at the cost of increasing the space and query time by n^{o(1)} factors. Note that there is also a trivial f -vertex cut oracle that simply applies the Nagamochi-Ibaraki sparsification [ NI92 ] and stores the resulting subgraph using \tilde{O}(\min\{m,fn\}) space and query time, and O(m) preprocessing time. As it turns out, combining Theorem 1.2 with the above trivial approach (i.e., using the former when f\leq\log n and the latter when f\geq\log n ) gives f -vertex cut oracles that are almost-optimal (up to n^{o(1)} factors), for every value of f . The almost-optimally of the preprocessing time is clear, so we focus only on space and query time in the following discussion. Space: We give an information-theoretic lower bound on the space occupied by the oracle, which is irrespective of preprocessing or query time. This lower bound holds also for the special case of minimum vertex cut oracles (i.e., where the graph is f -connected): Theorem 1.3 . Let n,f be positive integers such that 2\leq f\leq n/4 . Any f -vertex cut connectivity oracle must occupy \Omega\big(fn\cdot\log\big(\frac{n}{f}\big)\big) bits on some f -connected n -vertex graph. 3 3 3 If f>\frac{n}{4} , then a lower bound of \Omega(n^{2}) still holds, since an f -vertex cut oracle is also an f^{\prime} -vertex cut oracle for any f^{\prime}\leq f by definition. But in this case, the lower bound instance is not f -connected but only \Omega(f) -connected. , 4 4 4 Theorem 1.3 does not contradict the sparsification of [ NI92 ] , implying that G has a subgraph of O(fn) edges with exactly the same vertex cuts of size \leq f . By similar counting arguments as in the proof of Theorem 1.3 , one can show that \Omega(fn\log(f/n)) bits are required to represent an arbitrary graph with O(fn) edges in the worst case. For f=1 , the lower bound is \Omega(n) bits. As observed in [ DP20 ] , in the st variant a space lower bound of \Omega(fn) bits is easy to show by considering the subgraphs of the complete bipartite graph K_{n,f+1} . However, this does not yield a lower bound for the global variant. We therefore provide a different construction which yields a slightly stronger bound due to the extra \log(n/f) factor. We note that our lower bound also holds for the st variant of [ DP20 ] . (This holds as one can make n queries to the st -cut oracle of [ DP20 ] to determine if the queried set of vertices F is a cut.) Therefore the bound of Theorem 1.3 also strengthens the known bound of st -cut oracles. Query time: We first observe that lower bound construction of Long and Saranurak [ LS22a ] essentially also implies that the dependency on f in the query time of Theorem 1.2 cannot be made polynomial. Specifically, already for f=c\log n (where c is an absolute constant), any oracle with preprocessing time n^{2-o(1)} must have query time n^{1-o(1)} unless the Strong Exponential Time Hypothesis fails. 5 5 5 We note that the lower bound instance is a sparse graph with only O(fn)=\tilde{O}(n) edges, so the oracle of Theorem 1.2 preprocesses it with much less time than n^{2-o(1)} . Thus, for \Omega(\log n)\leq f\leq n^{o(1)} , we have almost matching lower and upper bounds of n^{1\pm o(1)} on the query time. In the regime f=o(\log n) , the query time in Theorem 1.2 is n^{o(1)} which trivially almost-optimal. Lastly, when f=n^{\alpha} for some constant \alpha\in(0,1] , we ask if the query time of O(fn) can be improved. As it turns out, the lower bound in [ LS22a ] shows that a polynomial improvement is unlikely, as it would refute the “online version” of the popular Orthogonal Vectors (OV) conjecture. This version has not been formally stated before, mainly because it did not find any concrete applications; nevertheless, it is considered plausible by the fine-grained complexity community [ Abb25 ] . The details regarding these query time lower bounds appear in Appendix A . On Incremental Updates. While our oracle focuses on decremental updates (namely, query connectivity upon the deletion of f vertices), it also makes sense to consider the incremental setting, where one “turns on” f vertices (the initial graph is given with some vertices turned on and some turned off). Allowing both decremental and incremental updates is commonly known as the sensitivity oracles setting, recently explored in the context of st vertex cut oracles [ LW24 ] where \operatorname{poly}(f,\log n) query time can be obtained for f -size update. Interestingly, for (global) vertex cut oracles, there is a strong separation between the decremental and incremental settings: using ideas from [ HLNV17 ] , we prove that even for f=O(1) , the required query time is at least n^{1-o(1)} in the incremental setting (assuming SETH). The details appear in Appendix B . Vertex Cut Labels. As for f -vertex cut labels, we essentially settle the questions posed by [ PPP24 , LPS25 ] by providing a construction with label length that matches the known lower bound up to polylogarithimic factors: Theorem 1.4 . For every n -vertex graph G=(V,E) and integer f=O(\log n) , there is an f -vertex cut labeling with label length of \tilde{O}(n^{1-1/f}) bits. The total label length (summing over all vertices) is \tilde{O}(n) bits. The labels are constructed deterministically in polynomial time. A nice aspect of the above labeling scheme is its (perhaps surprising) simplicity and black-box use of labels for the “ st variant” of the problem. When f=\Omega(\log n) , a randomized scheme with label length \tilde{O}(n) follows immediately by [ DP21 ] . However, the best current deterministic solution for this regime has labels of \tilde{O}(fn) bits, by using the standard graph sparsification of [ NI92 ] and storing the entire sparsified graph in the label of each vertex; we leave open the intriguing question of improving this trivial bound. We observe that although the structure of minimum vertex cuts can be leveraged to create exponentially faster oracles, it does not offer any advantage in the context of labels. This follows by observing that the label length lower bound of [ LPS25 ] holds also for f -connected graphs. Structural Insights: “Cut Respecting” Expander Decomposition. Many of the recent breakthrough algorithmic results for computing edge and vertex connectivity are based on some notion of hierarchical expander decomposition [ LP20 , Li21 , HLRW24 ] . The first connection between expanders and the minimum edge cut problem has been observed by [ KT15 , LP20 ] and in the data-structure setting by [ PT07 ] . The high-level approach is based on the observation that the problem at hand (e.g., computing a minimum cut, constructing vertex cut oracles, etc.) is considerably simpler when the graph is an expander. The hierarchical expander decomposition provides a convenient machinery to reduce general graphs to expanders. See e.g., [ Li21 , HLRW24 ] . Edge- and vertex-expander hierarchies have also been used recently for the st cut labeling schemes of [ LPS25 ] . Our f -vertex cut oracles are as well based on a variant of hierarchical expander decomposition admitting “cut respecting” properties. Very informally, it shows that every graph can be decomposed into a collection of terminal expanders of bounded total size, such that vertex cuts of size at most f “translate” into terminal cuts in these expanders. This structural decomposition is presented in Section 5 (see Definition 5.1 for a formal description); we are hopeful it could have future applications in various contexts (e.g., the distributed and parallel settings). Subsequent work. In a follow-up work, [ Kos25 ] employed a DFS-based, rather than expander-based approach for vertex cut oracles 6 6 6 The oracles of [ Kos25 ] also report the number of connected components. (it does not study vertex cut labels). For general graphs, their bounds shaves several logarithmic terms. For f -connected graphs (i.e., minimum vertex cut oracles), our query time and space bounds are considerably smaller, by factors of f and f^{2} , respectively (and as mentioned, our space bound is near-optimal). Our work also provides a collection of (possibly conditional) lower bounds for the problem which establish the almost optimality of our result. Organization. After a few preliminaries in Section 2 , the short, stand-alone Section 3 provides our f -vertex cut labeling scheme of Theorem 1.4 . We then move to consider f -vertex cut oracles, which comprises the majority of the paper. The main Section 4 is devoted to proving Theorems 1.2 and 1.1 ; a technical overview is given in the subsection 4.1 (a roadmap for the rest of the subsections appears at the end of the overview). Section 5 provides the formal details of the structural “cut respecting” expander decomposition. Section 6 proves the (unconditional) space lower bound of Theorem 1.3 . Conditional lower bounds are discussed in Appendices A and B , pertaining f -vertex cut oracles and their “incremental” variant, respectively. 2 Preliminaries Let G=(V,E) be an undirected n -vertex m -edge graph. The neighbor-set of a vertex v\in V is denoted by N(v) . When k\geq 0 is some nonnegative integer, N_{k}(v) denotes some fixed arbitrary subset of N(v) of size k (or N_{k}(v)=N(v) if |N(v)|\leq k ). For U\subseteq V , we define N(U)=(\bigcup_{u\in U}N(u))-U , i.e., N(U) are those vertices outside U with a neighbor in U . A vertex cut in G is a partition (L,S,R) of V such that L and R are nonempty, and there are no edges going between L and R . The set S is called the separator of the cut. Slightly abusing terminology, we call a vertex set F\subseteq V a cut in G if there exists some vertex cut in which F is the separator. Equivalently, F is a cut in G iff G-F (the subgraph of G induced on V-F ) is a disconnected graph. Let T\subseteq V be some set of vertices in G called terminals . A vertex cut (L,S,R) is called a vertex T -cut if L\cap T\neq\emptyset and R\cap T=\emptyset . In this case, we say that S separates T in G . Equivalently, S separates T in G iff there are two vertices s,t\in T-S which are disconnected in G-S . Again, slightly abusing terminology, we also call a vertex set F\subseteq V a T -cut in G if F separates T . We say that G is a (T,\phi) -expander with expansion 0<\phi\leq 1 , if for every vertex cut (L,S,R) in G , it holds that |S|\geq\phi\min\{|T\cap(L\cup S)|,|T\cap(R\cup S)|\} . The arboricity of G is the minimum number of forests into which its edges E can be partitioned. The f -connectivity certificates of Nagamochi and Ibaraki [ NI92 ] will be very useful for us. Theorem 2.1 ( [ NI92 ] ) . Let f\geq 1 . Then G has a subgraph H=(V,E_{H}) of arboricity at most f+1 (in particular |E_{H}|\leq(f+1)n ) with the following property: For every F\subseteq V with |F|\leq f and every s,t\in V-F , it holds that s,t are connected in H-F iff they are connected in G-F . The subgraph H can be computed deterministically in O(m) time. 3 Vertex Cut Labels Building Blocks. A basic building block in our f -vertex cut labels of Theorem 1.4 are succinct f -vertex failure connectivity labels ; these are the “ st cut” variant of f -vertex cut labels. Theorem 3.1 ( [ PPP24 , LPS25 ] ) . One can assign a label \ell(v) of \operatorname{poly}(f,\log n) bits to every v\in V such that, for every s,t\in V and F\subseteq V with |F|\leq f , it is possible to determine if s and t are connected in G-F by only inspecting the \ell(\cdot) labels of \{s,t\}\cup F . The \ell(\cdot) labels are constructed deterministically in polynomial time. The above theorem is highly non-trivial, but luckily we only use it as a black-box. Recall that in Theorem 1.4 we are interested in the regime f=O(\log n) , so the \ell(\cdot) labels have \tilde{O}(1) bits, which for us is essentially as succinct as unique vertex identifiers. From now on, whenever we “store a vertex v ”, we mean writing its unique identifier and its \ell(v) label, taking up only \tilde{O}(1) bits. Another building block is sparsification, a standard preliminary step in the area that is crucial for our approach here: by first applying the sparsification of [ NI92 ] (formally stated in Theorem 2.1 ), we may assume without loss of generality that G has at most (f+1)n edges. Warm-up: Minimum Vertex Cuts (The f -Connected Case). We first focus on the special case where G is f -connected, i.e., G does not have any vertex cuts of size f-1 or less. Our goal is to assign a label L(v) of \tilde{O}(n^{1-1/f}) bits to every v\in V , so that for every F=\{x_{1},\dots,x_{f}\}\subseteq V we can determine if F is a (minimum) vertex cut from the information stored in L(x_{1}),\dots,L(x_{f}) . This case turns out to be extremely simple and easy to present while conveying most of the intuition leading to the general case. The following claim is what makes the f -connected case so convenient: Claim 3.2 . Let F=\{x_{1},\dots,x_{f}\} be a vertex cut in an f -connected graph G . Then every x_{i}\in F has two neighbors that are separated by F . Proof. Seeking contradiction, suppose all the neighbors of x_{i} outside F are in the same connected component C of G-F (if N(x_{i})\subseteq F , choose C arbitrarily), and let D be a different connected component. Then N(D)\subseteq F-\{x_{i}\} is a vertex cut in G of size 0 . It can be improved to n^{1+o(1)} at the cost of increasing the space and query time of \mathcal{D} by n^{o(1)} factors. Given Theorem 4.2 , we can easily derive the f -vertex cut oracles of Theorem 1.2 : Proof of Theorem 1.2 . Define T_{0}=V . For i=1,2,\dots , apply Theorem 4.2 with input terminal set T_{i-1} , denoting the new terminal set by T_{i} and the resulting (f,T_{i-1},T_{i}) -cut detector by \mathcal{D}_{i-1} . Halt after the first iteration \ell that produced T_{\ell}=\emptyset ; we have \ell=O(\log n) as the size of the new terminal set halves in each iteration. The f -vertex cut oracle simply stores \mathcal{D}_{0},\mathcal{D}_{1},\dots,\mathcal{D}_{\ell-1} . Given query F\subseteq V s.t. |F|\leq f , the oracle queries each \mathcal{D}_{i} with F , and determines that F is a vertex cut in G if and only if some \mathcal{D}_{i}(F) returned “cut” . Indeed, if F is not a cut in G , the soundness in Definition 4.1 ensures that no \mathcal{D}_{i}(F) returns “cut” . Conversely, if F is cut in G , then let i be the largest index such that F separates T_{i} (note that 0\leq i\leq\ell-1 as F separates T_{0}=V but not T_{\ell}=\emptyset ); by the completeness in Definition 4.1 , \mathcal{D}_{i}(F) returns “cut” . The parameters (space, query and preprocessing time) of the resulting f -vertex cut oracle are only larger by an \ell=O(\log n) factor then those in Theorem 4.2 , which yields Theorem 1.2 . 7 7 7 The additive O(m) term in preprocessing time of Theorem 1.2 is for applying the standard sparsification of [ NI92 ] to reduce the number of edges in G to O(fn) . ∎ So, from now on we set our goal to prove Theorem 4.2 . We start by considering the case where the given graph is a terminal expander for which a solution follows readily by using the data-structure for st -cut variant. Then, we explain how to handle general graphs by reducing to terminal expanders. Warm-up: Terminal Expanders (or Few Terminals). We start by observing that Theorem 4.2 is easy to prove when G is a (T,\phi) -expander. In fact, in this case we can just take S^{*}=\emptyset , and reduce the query time to \operatorname{poly}(f,\log n)=\tilde{O}(1) . As usual, in the following the graph G=(V,E) has n vertices and m edges; The notation \bar{m} stands for \min\{m,fn\} . Lemma 4.3 (Terminal Expanders) . Suppose G is known to be a (T,\phi) -expander for T\subseteq V and 0<\phi\leq 1 . Then, there is a deterministic (f,T,\emptyset) -cut detector for G , denoted \mathsf{TEcutdet}(G,T,\phi,f) , with \tilde{O}(\bar{m}) space, \tilde{O}(f^{2}/\phi) query time, and m^{1+o(1)}/\phi+\tilde{O}(f\bar{m}) preprocessing time. The proof is based on the fact that the terminal expander G admits a low-degree Steiner tree for T ; this is a tree \tau in G that connects all terminals in T and has maximum degree \tilde{O}(1/\phi) , as was shown in [ LS22b , LPS25 ] . Consider a query F , and let N_{\tau}(F) be the set of neighboring vertices to F on the tree \tau . Then it suffices for us to decide whether all vertices in N_{\tau}(F) are connected in G-F : if so, then F does not separate T , and if not, then F is a cut in G . So answering the query F amounts to checking connectivity between \tilde{O}(|F|/\phi) vertices in G-F . This can be done efficiently by using an f -vertex failure connectivity oracle [ DP20 , LS22a , LW24 ] (i.e., st -cut oracles) which can be updated with a failure set F\subseteq V s.t. |F|\leq f , and subsequently can answer connectivity queries between pairs of vertices in G-F . In fact, f -vertex failure connectivity oracles also immediately yield trivial (f,T,\emptyset) -cut detectors, by updating with the query F and checking connectivity in G-F between all vertices in T (i.e., choosing an arbitrary terminal and checking if all other terminals are connected to it). This strategy is efficient when there are only few terminals. Lemma 4.4 (Few Terminals) . Let T\subseteq V . There is a deterministic (f,T,\emptyset) -cut detector for G , denoted \mathsf{FewTcutdet}(G,T) , with \tilde{O}(\bar{m}) space, \tilde{O}(f^{2})+O(f|T|) query time, and O(m)+\bar{m}^{1+o(1)}+\tilde{O}(f\bar{m}) preprocessing time. The formal proofs of Lemma 4.3 and Lemma 4.4 are in Section 4.2 . Of course, in the general case of Theorem 4.2 , G might not be a terminal expander and the terminal set T could be very large; the high-level strategy is recursively decomposing this general instance into many instances of terminal expanders (or graphs with few terminals), as we discuss next. The Left-Right Decomposition. On a high level, the divide-and-conquer decomposition approach is based on splitting the original instance (G,T) into two, according to a sparse vertex T -cut (L,S,R) , namely, such that |S| is much smaller than the number of terminals in L\cup S or in R\cup S ; such a cut exists as G is not a terminal expander. The splitting technique was introduced in [ SY22 ] for the case T=V , and extended to T\subseteq V in [ NSY23 ] (we further carefully adapt it to handle non-minimum cuts). The two new instances are called the f -left and f -right graphs G_{L} and G_{R} . The f -left graph G_{L} is (except in corner cases) just G[L\cup S] plus an additional “representative set” U_{R} of f+1 terminals from R , that are connected by a clique between themselves and by a biclique to S . G_{R} is defined symmetrically. Note that G_{L} and G_{R} are not necessarily subgraphs of G , but their vertex sets is a subset of V(G) . These graphs have two crucial properties that we term as cut-respecting properties : The “completeness” property is that together, G_{L} and G_{R} capture every T -cut F s.t. |F|\leq f , as long as F does not separate S . Namely, for such F , either the remaining part of F in G_{L} separates the remaining terminals there, or this will happen in G_{R} . Additionally, they also have “soundness” properties, ensuring that a vertex cut in G_{L} or G_{R} of size \leq f is also a cut in G (since V(G_{L}),V(G_{R})\subseteq V(G) , this is well-defined). Roughly speaking and ignoring some technical nuances, we keep on decomposing each of G_{L} and G_{R} recursively, until we get terminal expanders or instances with few terminals. The required new terminal set S^{*} for Theorem 4.2 is then defined as the union of separators S over all the sparse cuts that were found across the recursion. The cut-respecting properties imply that if F is a separator of T of size \leq f that is not captured by any leaf instance of the recursion, then F must also separate S^{*} , and so an (f,T,S^{*}) -cut detector can afford to return “fail” on F . The recursion is made effective and efficient by using a powerful tool devised in [ LS22a ] that finds a “good” sparse cut (L,S,R) . Intuitively, this sparse cut is promised to either cause the number of terminals to shrink (by some constant factor) in both G_{L} and G_{R} , or to cause terminal shrinking on one side while ensuring the other is an expander that requires no recursion. We call the resulting binary recursion tree \mathcal{T} the f -left-right decomposition tree ( f -LR tree, for short); storing the recursive instances in this tree serves the basis of our (f,T,S^{*}) -cut detector \mathcal{D} . The f -LR tree \mathcal{T} is shown to have the following key properties. • (Logarithmic depth) The depth of \mathcal{T} is O(\log|T|) . • (Near-linear space) Storing all the instances (G^{\prime},T^{\prime}) in the nodes of \mathcal{T} consumes \tilde{O}(n) space. • (Terminal reduction) The union S^{*} of all separators S from the sparse cuts (L,S,R) found in the internal nodes of \mathcal{T} is of size at most |T|/2 . Recall that the leaf instances in \mathcal{T} are terminal expanders or have few terminals, for which we can apply the efficient cut detectors of Lemma 4.3 and Lemma 4.4 , respectively. For a given F\subseteq V s.t. |F|\leq f , a natural query algorithm simply feeds F into all cut detectors in the leaves. The correctness is immediate by the cut-respecting properties of the left-right decomposition. Specifically, if F separates T but not S^{*} , then one of these must return cut “cut” ; and conversely, if one of them returns “cut” , then F must be a cut in G . The key limitation of this approach is in the query time which might be linear as there might be \Omega(n) leaves in \mathcal{T} that are explored. To obtain the desired \tilde{O}(2^{|F|}) query time, we devise a tree-searching procedure that essentially allows us to focus on only O(2^{|F|}) leaves. Tree Searching. Let us fix some query F\subseteq V s.t. |F|\leq f . Consider first the root node of \mathcal{T} , which is associated with the original instance (G,T) . The cut-respecting properties guarantee us that if F separates T but not S^{*} , then it is captured either by G_{L} in the left child or by G_{R} in the right child. But we cannot tell a priori which is the correct child, so it seems like we have to “branch” our search recursively to both the left and right subtrees of \mathcal{T} . As this phenomenon might reoccur in many nodes in our search, this could lead us to visit too many nodes in \mathcal{T} . However, in some cases, we do not have to branch. For example, what if F does not contain any vertex of G_{L} ? Then clearly, there is no point exploring the left child; we can “trim” the search on the left subtree and continue our search only in the right subtree. So intuitively, we want to trim as many recursive searches as we can to get faster query time. Let \mathcal{T}(F) denote the subtree of \mathcal{T} which is visited during the tree search for the query F . The “branch” nodes are those in \mathcal{T}(F) that have two children, and the “trim” nodes are those that have only one child. Our search mechanism ensures enough trimming so that the following property holds: If (G^{\prime},T^{\prime}) is an instance in some “branch” node, then |F\cap V(G^{\prime}_{L})|,|F\cap V(G^{\prime}_{R})|\leq|F\cap V(G^{\prime})|-1 . In other words, when moving from a “branch” node to its children, the size of the query decreases by at least 1 in both the left and the right child. As the original query at the root has size |F| , this implies that there are only O(2^{|F|}) “branch” nodes. So, as \mathcal{T}(F) only has depth O(\log|T|) , it can only contain O(2^{|F|}\log|T|) nodes. Consider again the root of \mathcal{T} , and suppose now that F\subseteq V(G_{L}) . We have to trim one of the subtree searches, as otherwise, the root would be a “branch” node violating the required property. Because F is consumed entirely in the left graph G_{L} , trimming the search in the right graph G_{R} seems more plausible. Note that G_{L} and G_{R} share only the vertices in S and in the representative terminal sets of the sides U_{L} and U_{R} . Thus, the part F\cap V(G_{R}) of F that survives in G_{R} must be contained in U_{L}\cup U_{R}\cup S . As we only care about detecting vertex cuts that do not separate S^{*}\supseteq S , this special structure of F\cap V(G_{R}) turns out to be enough for us to answer this query in G_{R} directly, without any further recursion. We term the relevant data structure to handle this case the “US cut detector” (where US stands for U=U_{L}\cup U_{R} and S ): Lemma 4.5 (US Cut Detectors) . Let G=(V,E) be a graph with n=|V| and m=|E| . Let U,S\subseteq V . There is an (f,V,S) -cut detector \mathsf{UScutdet}(G,U,S,f) which is restricted to answer queries F\subseteq S\cup U , |F|\leq f , with \tilde{O}(2^{|U|}fn) space, O(2^{|F|}f\log n) query time, and O(2^{|U|}(m+fn\log n)) preprocessing time. Further, if G is known to be f -connected, the query time improves to O(f\log n) . The proof is found in Section 4.2 . So, by augmenting the root with \mathsf{UScutdet}(G_{R},U_{L}\cup U_{R},S,f) , we can just query this cut detector with F\cap V(G_{R}) and trim the recursive search in the right subtree. Of course, there is nothing special about the root, or about its right child; we augment all nodes in \mathcal{T} with US cut detectors for trimming searches in their left or right children. Improving Space and Preprocessing Time. There is one small caveat with the approach described above: the O(2^{|U|}) factors in the space and preprocessing time of Lemma 4.5 lead to corresponding factors of O(2^{2f}) in the space and preprocessing time of \mathcal{D} in Theorem 4.2 , and hence of the entire oracle in Theorem 1.2 (as we use U-sets of the form U_{L}\cup U_{R} , that have size up to 2f+2 ). On a high level, these are shaved by applying “hit-miss hashing” tools [ KP21 ] , allowing us to essentially focus only on the case where query F does not contain any terminals from T . As U_{L}\cup U_{R}\subseteq T (except in technical corner cases), this means that whenever we use a US cut detector, the query is actually contained in the S-set. Thus, we can construct this oracle with an empty U-set instead. Minimum Vertex Cuts. The oracle of Theorem 1.1 is obtained by slightly tweaking the general construction to take advantage of the structural properties of minimum vertex cuts. When the graph G is f -connected, one can show an even stronger “completeness” property of the left and right graphs: If F separates T but not S , then either (1) F\subseteq L\cup S and F separates T in G_{L} , or (2) F\subseteq R\cup S and F separates T in G_{R} . This property allows us to completely eliminate the need to branch in the tree-searching process for query F . First, if F intersects both L and R , then it cannot be that F separates T but does not separate S^{*}\supseteq S , so we can safely return “fail” . Next, if F intersects L and not R (resp., R and not L ), we only have to recursively search the left (resp., right) subtree. Otherwise, we have F\subseteq S , and then we can use US cut detectors to trim the searches in both the left and right subtrees. Thus, the resulting tree search process visits only a path in \mathcal{T} , which eliminates the 2^{f} factor in the query time that appeared in the general case. We remark that in fact, it suffices for the query to be a “minimal” cut in G (in a properly defined sense) for the above arguments to work, even if the graph G is not f -connected. Roadmap. We first provide the cut detectors for special cases (terminal expanders, few terminals, US) in Section 4.2 . Next, we formally discuss left and right graphs and their properties in Section 4.3 . The following Section 4.4 presents the recursive left-right decomposition producing the tree \mathcal{T} and the new terminal set S^{*} . Then, Section 4.5 formally discusses the construction of and query algorithm of the (f,T,S^{*}) -cut detector \mathcal{D} of Theorem 4.2 (without shaving the O(2^{2f}) factors in preprocessing time and space). The modifications that yield improved results when G is f -connected are described next, in Section 4.6 . Finally, Section 4.7 explains how the O(2^{2f}) factors in the preprocessing and query time from Section 4.5 can be shaved. 4.2 Special Cut Detectors This section presents some special cut detectors, which essentially form the “base cases” of the recursive approach that used to create the cut detectors for general graphs of Theorem 4.2 , as overviewed in Section 4.1 . Throughout this section, G=(V,E) is a connected graph with n vertices and m edges, f\geq 1 is an integer parameter, and \bar{m}=\min\{m,fn\} . As a basic building block, we use efficient f -vertex failure connectivity oracles as a black box. Such an oracle for G can be updated with any set F\subseteq V of size |F|\leq f . Once updated, the oracle can receive queries of vertex pairs (s,t)\in V\times V , which are answers by indicating whether s,t are connected in G-F . We will use the current state-of-the-art, given by [ LW24 ] : Theorem 4.6 ( [ LW24 , Theorem 1] ) . There is an f -vertex failure connectivity oracle for G with \tilde{O}(\bar{m}) space, \tilde{O}(f^{2}) update time, and O(f) query time. The oracle can be constructed deterministically in O(m)+\bar{m}^{1+o(1)}+\tilde{O}(f\bar{m}) time. As a direct corollary, we get Lemma 4.4 concerning the “few terminals” case. See 4.4 Proof. We simply use the f -vertex failure oracle connectivity oracle \mathcal{O} of Theorem 4.6 , and also store T . Given a query F\subseteq V with |F|\leq f , we first update \mathcal{O} with F , and then apply |T-F|-1 connectivity queries (s,t) , where s is some fixed terminal in T-F , and t ranges over the remaining terminals from T-F . Note that F separates T iff s is disconnected from some other t\in T-F , in which case we answer “cut” ; otherwise we answer “fail” . ∎ Next, we consider the case of terminal expanders in Lemma 4.3 : See 4.3 Proof. As G is a (T,\phi) -expander, we can apply the deterministic, (m^{1+o(1)}/\phi) -time algorithm of [ LS22b , Lemma 5.7] , that computes a Steiner tree \tau for T with maximum degree O(\log^{2}n/\phi) . 8 8 8 The degree bound can be improved to O(1/\phi) at the cost of spending O(mn\log n) time to compute \tau , as shown in [ LPS24 ] . Since we incur some logarithmic factors anyway, we prefer the faster running time. Additionally, we compute the oracle \mathcal{O} of Theorem 4.6 for G . The cut detector \mathsf{TEcutdet}(G,T,f) simply stores \tau and \mathcal{O} . The stated space and prepossessing time follow immediately. Given a query F\subseteq V with |F|\leq f , we first update \mathcal{O} with the set F as the faults. Next, we compute the \tau -neighbors of F , namely all the vertices appearing in N_{\tau}(x) for some x\in F (where N_{\tau}(x)=\emptyset if x\notin V(\tau) ). We choose one arbitrary non-faulty vertex v^{*}\notin F which is \tau -neighbor of F (if no such exist, we return “fail” ). Finally, we query \mathcal{O} with (v^{*},u) for every other non-faulty u\notin F which is a \tau -neighbor of F . If one of these queries returned that v^{*},u are disconnected in G-F , we return “cut” ; otherwise we return “fail” . The soundness of this procedure is clear, as we only return “cut” in case we find a pair of disconnected vertices in G-F . For the completeness, suppose F separates T , and let t,t^{\prime}\in T-F be two terminals separated by F . Consider the path P in \tau between t and t^{\prime} . As F separates t from t^{\prime} , F must intersect P . Let x and x^{\prime} be the vertices in F\cap V(P) that are closest to t and t^{\prime} , respectively. Let u and u^{\prime} be the neighbors of x and x^{\prime} in the directions of t and t^{\prime} , respectively. Note that u and u^{\prime} are different (even if x=x^{\prime} ), and are both non-faulty \tau -neighbors of F . Also, the segments of P between t and u , and between t^{\prime} and u^{\prime} , are both present in G-F . Hence, as t and t^{\prime} are disconnected in G-F , so are u and u^{\prime} . Therefore, one of the queries (v^{*},u) and (v^{*},u^{\prime}) to \mathcal{O} must return that the pair is disconnected in G-F , so we return “cut” on F , as required. Finally, we address the query time. Updating \mathcal{O} with F takes \tilde{O}(f^{2}) time, and then each subsequent query to \mathcal{O} takes O(f) time. As the maximum degree in \tau is O(\log^{2}n/\phi) , F can have at most O(f\log^{2}n/\phi) of \tau -neighbors, which means that there are O(f\log^{2}n/\phi) queries to \mathcal{O} . So we get a total query time of \tilde{O}(f^{2}/\phi) . ∎ We end this section by describing how US cut detectors are constructed. This relies on the following short structural lemma. Lemma 4.7 . Let S\subseteq V . Then for every F\subseteq V , F is a cut in G if and only if (at least) one of the following options holds: 1. F separates S in G . 2. F\supseteq S and G-(S\cup F) is disconnected. 3. F\not\supseteq S and G-(S\cup F) has a connected component C with N(C)\subseteq F (here N(C) refers to the neighbor set of C in G ). Proof. The “if” direction: If option 1 holds then of course F is a cut. If option 2 holds, then G-F=G-(S\cup F) and the latter is disconnected, so F is a cut. If option 3 holds, then F separates some u\in S-F from any v\in C , so F is a cut. The “only if” direction: Assume F is a cut. If option 1 holds we are done, so suppose F does not separate S . If F\supseteq S , then G-(S\cup F)=G-F and the latter is disconnected, so option 2 holds. If F\not\supseteq S , let D be the connected component of G-F such that S-F\subseteq D (which exists since F does not separate S ), and let C\neq D be a different connected component of G-F (which exists since F is a cut). Then clearly N(C)\subseteq F . Note that C does not intersect S , since S\subseteq F\cup D . Thus, C remains connected in (G-F)-S=G-(S\cup F) , so it must also be a connected component of G-(S\cup F) . Namely, we have shown that option 3 holds. ∎ We are now ready to (restate and) prove Lemma 4.5 : See 4.5 Proof. First, \mathsf{UScutdet}(G,U,S,f) stores U and S . Next, for every W\subseteq U , it stores the collection of all neighbor-sets N(C) of connected components C in G-(S\cup W) such that |N(C)|\leq f . (Again, here N(C) refers to the neighbor set of C in G .) This collection is stored in a sorted array, where each set is represented by a bitstring of length O(f\log n) , formed by concatenating the IDs of the vertices in the set (in sorted order). Additionally, it stores a single bit which indicates if G-(S\cup W) is connected. The space needed for a specific W\subseteq U is dominated by its corresponding array, which takes up O(fn) words. The preprocessing time needed for W is O(m+fn\log n) , as the collection of relevant sets N(C) is easy to compute in O(m) time, and sorting the array takes O(f\cdot n\log n) time (again, we multiply by f to account for the comparison between elements of f words). Summing over W gives the desired space and preprocessing bounds. To answer a query F\subseteq S\cup U with |F|\leq f , we consider W=F-S\subseteq U , and note that S\cup F=S\cup W . So, in light of Lemma 4.7 , we do the following: If F\supseteq S and G-(S\cup W) is disconnected, return “cut” ; If F\not\supseteq S and the array of W contains some subset F^{\prime}\subseteq F , return “cut” ; Otherwise, return “fail” . The soundness and completeness guarantees follow immediately from Lemma 4.7 . The query time is dominated by the second part, where we need to go over all subsets of F , and check if they appear in the sorted array corresponding to W . Each such check takes O(f\log n) time, as we do a binary search in an array of length \leq n , where each element is represented by f (or less) words. So, the query time is O(2^{|F|}\cdot f\log n) . The improvement in query time when G is f -connected is because in this case, the array of W cannot contain a neighbor set N(C) with |N(C)|1$,}\quad\text{and }r:=O(1). (1) These fixed values of \epsilon and r are used in every invocation of Lemma 4.13 . Thus, the corresponding expansion parameter from this lemma is always at least \phi:=\frac{\epsilon}{(\log n)^{O(r^{5})}}=\frac{1}{\operatorname{poly}\log n} (2) Note that for any constant \delta>0 we can take r to be a sufficiently large constant (depending only on \delta ) to get running time m^{1+\delta} in Lemma 4.13 . We now describe algorithm for constructing \mathcal{T} . We initialize \mathcal{T} to have only a root node associated with (G,T) . We then apply a recursive procedure from this root. In general, each recursive call is given a node q which is a leaf in the current state of \mathcal{T} , and either decides to make q a permanent leaf (and end the current recursive branch), or creates new children nodes for q and applies recursive calls on (some or all of) them. The recursive call on q is implemented as follows. First, if |T_{q}|\leq(f+1)/\epsilon , then q is set to be a permanent leaf in \mathcal{T} , and the call is terminated. Otherwise, we apply Lemma 4.13 on G_{q} and get the cut (L_{q},S_{q},R_{q}) . We then construct the f -left and f -right graphs of (G_{q},T_{q}) w.r.t. (L_{q},S_{q},R_{q}) , denoted G_{L_{q}} and G_{R_{q}} respectively. We also denote by U_{L_{q}} and U_{R_{q}} the sets of Definition 4.8 used to construct these graphs. Additionally, let U_{S_{q}} be an arbitrary set of f+1 terminals from T_{q}\cap S_{q} (or all of T_{q}\cap S_{q} if |T_{q}\cap S_{q}|\leq f+1 ). The algorithm now proceeds according to the two cases of Lemma 4.13 : (Balanced) If |T_{q}\cap(L_{q}\cup S_{q})|,|T_{q}\cap(R_{q}\cup S_{q})|\geq\frac{1}{3}|T_{q}| : We then create two children for q : • A left child q_{l} associated with (G_{L_{q}},T_{q}\cap V(G_{L_{q}})) • A right child q_{r} associated with (G_{R_{q}},T_{q}\cap V(G_{R_{q}})) . We then apply the algorithm recursively on both q_{l} and q_{r} . (Expander) Else, we know that |T_{q}\cap R_{q}|\geq\frac{1}{2}|T_{q}| and that G_{q}[R_{q}] is a (T_{q}\cap R_{q},\phi) -expander. In this case, we create three children for q : • A left child q_{l} associated with (G_{L_{q}},T_{q}\cap V(G_{L_{q}})) • A right child q_{r} associated with (G_{R_{q}},T_{q}\cap R_{q}) . • An additional stepchild q_{s} associated with (G_{R_{q}},U_{L_{q}}\cup U_{R_{q}}\cup U_{S_{q}}) We then apply the algorithm recursively only on q_{l} ( q_{r},q_{s} are permanent leaf nodes). Remark 4.14 . The right child q_{r} is associated with G_{R_{q}} in both cases, but its terminal set is defined slightly differently. In the balanced case, we simply take all terminals of T_{q} found in G_{R_{q}} ; in the expander case, we only take the terminals from R_{q} . This subtle distinction is to ensure that in the latter case, the instance at q_{r} is indeed a terminal expander, as G_{q}[R_{q}] is a (T_{q}\cap R_{q},\phi) -expander, and G_{R_{q}} is a supergraph of G_{q}[R_{q}] (while G_{R_{q}} might not be an expander w.r.t. all the T_{q} -terminals in it). The point of the additional “stepchild” q_{s} is essentially to account for this loss of terminals in the right child, by using Lemma 4.11 . Finally, we define the set S^{*} for Theorem 4.2 as the union of all separators S_{q} from the cuts associated with internal nodes of \mathcal{T} : S^{*}:=\bigcup\big\{S_{q}\mid\text{$q\in\mathcal{V}$ is an internal node of $\mathcal{T}$}\big\}. (3) Analysis. We now prove the key properties of the f -LR tree \mathcal{T} : Lemma 4.15 . Let \mathcal{T}=(\mathcal{V},\mathcal{E}) be the LR-tree for (G,T) and let S^{*} be the union of separators associated with nodes of \mathcal{T} as defined in Equation 3 . Then all of the following properties hold. 1. (Expander/small leaf-nodes) Let q be a leaf node in \mathcal{T} associated with (G_{q},T_{q}) . Then either (i) G_{q} is a (T_{q},\phi) -expander, or (ii) |T_{q}|=O(f/\epsilon) . (See Equations 1 and 2 for \epsilon and \phi .) 2. (Logarithmic depth) The depth of \mathcal{T} is d=O(\log|T|) . 3. (Terminal reduction) |S^{*}|\leq\frac{1}{2}|T| . 4. (Near-linear space) \sum_{q\in\mathcal{V}}|V(G_{q})|=O(nd) and \sum_{q\in\mathcal{V}}|E(G_{q})|=O(fnd^{2}) . The rest of this section is devoted to proving the above Lemma 4.15 . Observe that Property 1 regarding the leaves of \mathcal{T} follows immediately from the description of the algorithm and the discussion in Remark 4.14 . (Note that a “stepchild” of the form q_{s} is a leaf node associated with at most 3(f+1)\leq O(f/\epsilon) terminals, as |U_{L_{q}}|,|U_{R_{q}}|,|U_{S_{q}}|\leq f+1 .) For the remaining properties, we need the following two claims. In both, q refers to some internal node in \mathcal{T} . Hence, q has left and right children q_{l} and q_{r} (and possibly also a stepchild q_{s} which is a leaf in \mathcal{T} ). Recall that because q is not a leaf, we must have |T_{q}|>(f+1)/\epsilon , so f+1<\epsilon|T_{q}| . Also, recall that |S_{q}|\leq\epsilon|T_{q}| by Lemma 4.13 , and that |U_{L_{q}}|,|U_{R_{q}}|\leq f+1 by Definition 4.8 . These facts will serve us in both proofs. Claim 4.16 . Let q be an internal node in \mathcal{T} . Then it holds that |T_{q_{l}}|\leq 0.9|T_{q}| . Additionally, if q_{r} is an internal node in \mathcal{T} , then also |T_{q_{r}}|\leq 0.9|T_{q}| . Proof. Suppose first that the balanced case occurred in the recursive call initiated at q . Then we have |T_{q}\cap(R_{q}\cup S_{q})|\geq\frac{1}{3}|T_{q}| , and hence |T_{q}\cap L_{q}|\leq\frac{2}{3}|T_{q}| . We thus get |T_{q_{l}}|=|T_{q}\cap V(G_{L_{q}})|=|T_{q}\cap L_{q}|+|T_{q}\cap S_{q}|+|T_{q}\cap U_{R_{q}}|\leq\left(\frac{2}{3}+2\epsilon\right)|T_{q}|\leq 0.9|T_{q}|. Additionally, in the balanced case we also have |T_{q}\cap(L_{q}\cup S_{q})|\geq\frac{1}{3}|T_{q}| , so a symmetric argument proves that also |T_{q_{r}}|\leq 0.9|T_{q}| . It the expander case q_{r} is a leaf, so we only have to care about |T_{q_{l}}| . But in this case we have |T_{q}\cap R_{q}|\geq\frac{1}{2}|T_{q}| , so in particular |T_{q}\cap(R_{q}\cup S_{q})|\geq\frac{1}{3}|T_{q}| , and the same calculation from the balanced case goes through. ∎ Claim 4.17 . Let q be an internal node in \mathcal{T} . Then the following inequalities hold: |V(G_{q_{l}})|+|V(G_{q_{r}})|\leq(1+3\epsilon)|V(G_{q})|, (4) |T_{q_{l}}|+|T_{q_{r}}|\leq(1+3\epsilon)|T_{q}|. (5) Proof. Recall that G_{q_{l}}=G_{L_{q}} and G_{q_{r}}=G_{R_{q}} . So, |V(G_{q_{l}})|+|V(G_{q_{r}})| counts twice the vertices in S_{q}\cup U_{L_{q}}\cup U_{R_{q}} , and counts once every other vertex in G_{q} . We get |V(G_{q_{l}})|+|V(G_{q_{r}})|\leq|V(G_{q})|+|S_{q}|+2(f+1)\leq|V(G_{q})|+3\epsilon|T_{q}|\leq(1+3\epsilon)|V(G_{q})| which proves Equation 4 . The proof of Equation 5 is omitted: it is essentially identical, only now counting the terminals of T_{q} that are found in the f -left and f -right graphs G_{L_{q}} and G_{R_{q}} . ∎ We are now ready to show the remaining properties of Lemma 4.15 (Properties 2 , 3 and 4 ). We start with Property 2 : that \mathcal{T} has depth d=O(\log|T|) follows from Claim 4.16 , implying that when walking down from the root of \mathcal{T} to its deepest leaf, the number of terminals associated with the current node, which starts at |T| , shrinks by a 0.9 factor in every step (except maybe the last). Next, we prove Property 3 , bounding the size of |S^{*}| . Let \mathcal{V}_{i} denote the set of nodes with depth i in \mathcal{T} . By inductively using Equation 5 , we obtain that for every i\in\{0,1,\dots,d\} , \sum_{\text{internal $q\in\mathcal{V}_{i}$}}|T_{q}|\leq(1+3\epsilon)^{i}|T| (here, we used the fact that stepchildren nodes cannot be internal in \mathcal{T} ). Recall that for every internal q\in\mathcal{V} we have |S_{q}|\leq\epsilon|T_{q}| by Lemma 4.13 , so we obtain |S^{*}|\leq\sum_{\text{internal $q\in\mathcal{V}$}}|S_{q}|\leq\sum_{i=1}^{d}\sum_{\text{internal $q\in\mathcal{V}_{i}$}}\epsilon|T_{q}|\leq\epsilon\Big(\sum_{i=1}^{d}(1+3\epsilon)^{i}\Big)|T|=\frac{(1+3\epsilon)^{d+1}-1}{3}|T|\leq\frac{1}{2}|T|, where in the last inequality, we use that d=O(\log|T|) (as proved in Property 2 ), so we can choose the constant c in Equation 1 to be large enough so as to make (1+3\epsilon)^{d+1}\leq 2.5 . Finally, we show Property 4 . Let \widehat{\mathcal{V}}_{i} denote the subset of \mathcal{V}_{i} that contains all the nodes with depth i in \mathcal{T} that are not stepchildren. By inductively using Equation 4 , we obtain that for every i\in\{0,1,\dots,d\} , \sum_{q\in\widehat{\mathcal{V}}_{i}}|V(G_{q})|\leq(1+3\epsilon)^{i}n\leq O(n), where the last inequality follows from i\leq d=O(\log|T|) and the choice of \epsilon in Equation 1 . Now, recall that each stepchild has the same number of vertices as its sibling right child (as they are both associated with the same graph, but with different terminals). Therefore, we get \sum_{q\in\mathcal{V}}|V(G_{q})|=\sum_{i=1}^{d}\sum_{q\in\mathcal{V}_{i}}|V(G_{q})|\leq\sum_{i=1}^{d}\Big(2\sum_{q\in\widehat{\mathcal{V}}_{i}}|V(G_{q})|\Big)\leq O(nd). Next, by inductively applying Observation 4.12 , and recalling that the root of \mathcal{T} is associated G , whose arboricity is at most f+1 , we see that if q\in\mathcal{V}_{i} then G_{q} has arboricity at most (i+1)(f+1) , and hence at most |E(G_{q})|\leq(i+1)(f+1)|V(G_{q})|\leq O(df)\cdot|V(G_{q})| . So, summing over all nodes in \mathcal{T} , we get \sum_{q\in\mathcal{V}}|E(G_{q})|=O(df)\cdot\sum_{q\in\mathcal{V}}|V(G_{q})|=O(df)\cdot O(nd)=O(fnd^{2}). This concludes the proof of Lemma 4.15 . 4.5 The Terminal Cut Detector \mathcal{D} of Theorem 4.2 Let G , T and f be the same as in the previous Section 4.4 . This last section discussed how to find the set S^{*} for Theorem 4.2 by constructing the f -LR tree \mathcal{T} constructed for (G,T) . In this section, we complete the proof of Theorem 4.2 by providing the construction of the (f,T,S^{*}) -cut detector \mathcal{D} by using the f -LR tree \mathcal{T} and the specialized cut detectors from Section 4.2 . Constructing \mathcal{D} . The construction starts by computing the f -LR tree \mathcal{T} for (G,T) and the corresponding new terminal set S^{*} (defined in Equation 3 ). The next step is augmenting each leaf node q of \mathcal{T} , associated with (G_{q},T_{q}) , with a corresponding specialized (f,T_{q},\emptyset) -cut detector. By Lemma 4.15 ( 1 ), either |T_{q}|=O(f/\epsilon) , or G_{q} is a (T_{q},\phi) -expander (with \phi as in Equation 2 ). So, if the former option holds, we can use \mathsf{FewTcutdet}(G_{q},T_{q},f) ; otherwise we use \mathsf{TEcutdet}(G_{q},T_{q},\phi,f) . Next, we augment the internal nodes of \mathcal{T} with specialized US cut detectors. Let q be an internal node in T , associated with (G_{q},T_{q}) and with the vertex cut (L_{q},S_{q},R_{q}) in G . Let G_{L_{q}} and G_{R_{q}} be the corresponding f -left and f -right graphs, and U_{L_{q}} and U_{R_{q}} as in Definition 4.8 . The node q will be augmented with two US cut detectors: \mathsf{UScutdet}(G_{L_{q}},U_{L_{q}}\cup U_{R_{q}},S_{q},f) and \mathsf{UScutdet}(G_{R_{q}},U_{L_{q}}\cup U_{R_{q}},S_{q},f) . Note that both have the same “S-set” S_{q} and the same “U-set” U_{L_{q}}\cup U_{R_{q}} , but they are constructed with respect to the different graphs G_{L_{q}} and G_{R_{q}} . When we finish augmenting all the nodes in \mathcal{T} as described above, we no longer need to explicitly store the graphs G_{q} in each node q . Instead, we just store V(G_{q}) , and (in case q is internal) its partition into the cut (L_{q},S_{q},R_{q}) and the sets U_{L_{q}} and U_{R_{q}} . We keep storing the associated terminal set T_{q} . Each of these vertex subsets is stored in some data structure supporting membership queries in \tilde{O}(1) time. 9 9 9 We can use perfect hashing to get constant query time for membership queries. However, as we already incur other logarithmic factors, a balanced binary search tree or a sorted array will suffice for us. This concludes the construction of \mathcal{D} . Query Algorithm of \mathcal{D} . We now describe how the (f,T,S^{*}) -cut detector \mathcal{D} answers a given query F\subseteq V with |F|\leq f . The query algorithm explores \mathcal{T} in a recursive manner, which is initialized from the root of \mathcal{T} . In each visited node q , the recursive call associated with q returns either “cut” or “fail” , and the final answer is the value returned by the initial call to the root. We denote F_{q}=F\cap V(G_{q}) , and when q is an internal node in \mathcal{T} , F_{l}=F\cap V(G_{L_{q}}) and F_{r}=F\cap V(G_{R_{q}}) . Note that F_{q_{l}}=F_{l} , F_{q_{r}}=F_{r} , and F_{q_{s}}=F_{r} when q_{s} exists. The recursion is implemented as follows: (“Leaf”) If q is a leaf: Then we query the (f,T_{q},\emptyset) -cut detector of G_{q} which is found in q (which is either \mathsf{FewTcutdet}(G_{q},T_{q},f) or \mathsf{TEcutdet}(G_{q},T_{q},\phi,f) ) with F_{q} , and return the answer obtained from this query. (“Trim Right”) Else, if F_{q}\cap R_{q}\subseteq U_{R_{q}} : Then we have F_{r}\subseteq S_{q}\cup U_{L_{q}}\cup U_{R_{q}} . Hence, we can query \mathsf{UScutdet}(G_{R_{q}},U_{L_{q}}\cup U_{R_{q}},S_{q},f) with F_{r} . • If this query returns “cut” , we return “cut” . • Otherwise, we recurse only on the left child q_{l} . If this recursive call returned “cut” , we return “cut” ; otherwise we return “fail” . (“Trim Left”) Else, if F_{q}\cap L_{q}\subseteq U_{L_{q}} : Then in a similar fashion to the previous case, we can query \mathsf{UScutdet}(G_{L_{q}},U_{L_{q}}\cup U_{R_{q}},S_{q},f) with F_{l} . • If this query returns “cut” , we return “cut” . • Otherwise, we recurse on the right child q_{r} and on the stepchild q_{s} (if exists). If at least one recursive call returned “cut” , we return “cut” ; otherwise we return “fail” . (“Branch”) Else: We recurse on all children of q . If at least one recursive call returned “cut” , we return “cut” ; otherwise we return “fail” . We denote by \mathcal{T}(F) the query tree of F , induced by \mathcal{T} on the nodes visited during the query; note that \mathcal{T}(F) is connected and contains the root of \mathcal{T} . Correctness. We will show the following by induction from the leaves upwards on \mathcal{T}(F) : Lemma 4.18 . The answer returned from a recursive call invoked on a node q in \mathcal{T}(F) satisfies: • (Soundness) If the answer is “cut” , then F_{q} is a cut in G_{q} . • (Completeness) If F_{q} separates T_{q} but not S^{*}\cap V(G_{q}) in G_{q} , then “cut” is returned. The correctness of the (f,T,S^{*}) -cut detector \mathcal{D} immediately follows by taking q as the root of \mathcal{T} in Lemma 4.18 . The argument hinges on the completeness and soundness properties of left and right graphs proved in Lemma 4.9 and Lemma 4.10 . We now give the full proof. Proof of Lemma 4.18 . The “Leaf” case serves as the base case for the induction: then, we return the answer of an (f,T_{q},\emptyset) -cut detector in G_{q} on the query F_{q} , so both the soundness and completeness properties clearly hold. From now on, assume that q is an internal node. We start by showing the soundness property. Observe that a “cut” answer from q can happen only if “cut” was returned from some recursive call invoked from a child of q , which is associated with G_{L_{q}} or G_{R_{q}} , or if some US cut detector built for G_{L_{q}} or G_{R_{q}} returned “cut” . Such “cut” answers are sound, either by induction hypothesis or by the correctness of US cut detectors from Lemma 4.5 . Namely, “cut” can be returned at q only in case F_{l} is a cut in G_{L_{q}} or F_{r} is a cut in G_{R_{q}} , and Lemma 4.10 implies that F_{q} is indeed cut in G_{q} in this case. We now show the completeness property, so assume F_{q} separates T_{q} but not S^{*}\cap V(G_{q}) in G_{q} . First, by Lemma 4.9 , we have that either (i) F_{l} separates T_{q}\cap V(G_{L_{q}}) in G_{L_{q}} , or (ii) F_{r} separates T_{q}\cap V(G_{R_{q}}) in G_{R_{q}} . These cases are almost symmetric, except (ii) introduces a slight complication due to the possible existence of a stepchild q_{s} . So, we will consider both cases: (i) The contrapositive of Lemma 4.10 implies that F_{l} does not separate S^{*}\cap V(G_{L_{q}}) in G_{L_{q}} . In particular, by Equation 3 , F_{l} does not separate S_{q} in G_{L_{q}} . In the “Trim Right” case, we query the (f,V(G_{L_{q}}),S_{q}) -cut detector with F_{l} , so it must return “cut” . In the remaining cases, a recursive call is invoked from q_{l} (or “cut” is already returned and we are done). This call must return “cut” by the induction hypothesis and the discussion above. So, in any case, the call from q also returns “cut” . (ii) By symmetric arguments as (i), F_{r} does not separate S^{*}\cap V(G_{R_{q}}) nor S_{q} in G_{R_{q}} . Further, the “Trim Left” case must return “cut” . In the remaining cases, recursive calls are invoked from q_{r} and from the stepchild q_{s} if it exists (or “cut” is already returned and we are done). So, it suffices to show that one of these calls must return “cut” . If the stepchild q_{s} doesn’t exist, the argument is symmetric to case (i), so assume q_{s} exists. If F_{r} separates T_{q}\cap R_{q} in G_{R_{q}} , then the call on q_{r} must return “cut” by induction hypothesis. Otherwise, by Lemma 4.11 , F_{r} separates U_{L_{q}}\cup U_{S_{q}}\cup U_{R_{q}} in G_{R_{q}} , so the call on q_{s} must return “cut” by induction hypothesis. In any case, this means we return “cut” . The proof of Lemma 4.18 is concluded. ∎ Query Time. We now analyze the query time, hinging on the following lemma: Lemma 4.19 . Consider a subtree of the query tree \mathcal{T}(F) rooted at some node q , and let x\geq 0 be an integer. The number of “Branch” node q^{\prime} such that |F_{q^{\prime}}|=x in this subtree is at most 2^{|F_{q}|-x} . Proof. By induction on the height of \mathcal{T}_{q}(F) . We split to cases according to q ’s type: (”Leaf”) Trivial, as q ’s subtree has 0 “Branch” nodes (and 0\leq 2^{|F_{q}|-x} ). (“Trim Right”) Then the “Branch” nodes in q ’s subtree are exactly those from q_{l} ’s subtree. So by induction, the number of such nodes q^{\prime} with |F_{q^{\prime}}|=x is at most 2^{|F_{l}|-x}\leq 2^{|F_{q}|-x} . (“Trim Left”) Symmetric to the “Trim Left” case above. (Note that even if q_{s} exists, it is a leaf, so its subtree cannot contribute to “Branch” nodes.) (“Branch”) Then we have F_{q}\cap R_{q}\not\subseteq U_{R_{q}} (since q is not “Trim Right”). Hence (by Definition 4.8 of f -left graphs), at least one vertex in F_{q} is missing from F_{l} (this is some vertex in F\cap R_{q}-U_{R_{q}} ), so |F_{l}|\leq|F_{q}|-1 . A symmetric argument gives that |F_{r}|\leq|F_{q}|-1 . We now consider cases according to the value of x : When x>|F_{q}| , the subtree of q cannot have a node with an associated query of size x (and 0\leq 2^{|F_{q}|-x} ). When x=|F_{q}| , the root q is the only “Branch” node in its subtree with an associated query of size x (and 1=2^{|F_{q}|-x} ). When 0\leq x<|F_{q}| , then “Branch” nodes with associated query of size x in q ’s subtree can come only from the subtrees of q_{l} and q_{r} (again, if q_{s} exists, it is a leaf). By induction hypothesis, we obtain that these are at most 2^{|F_{l}|-x}+2^{|F_{r}|-x}\leq 2\cdot 2^{|F_{q}|-1-x}=2^{|F_{q}|-x} . ∎ Recall d=O(\log|T|) is the depth of the f -LR tree \mathcal{T} (see Lemma 4.15 ). We now get: Corollary 4.20 . The following hold for the query tree \mathcal{T}(F) : 1. \mathcal{T}(F) has O(d\cdot 2^{|F|-x}) “Trim” nodes q such that |F_{q}|=x , for every 0\leq x\leq|F| . 2. \mathcal{T}(F) has O(d\cdot 2^{|F|}) nodes overall. Proof. We let each ‘Trim” node q such that |F_{q}|=x to choose as representative its nearest ancestor “Branch” node b(q) in \mathcal{T}(F) (if there is no such ancestor, let b(q) be the root of \mathcal{T}(F) ). Then each chosen b(q) has |F_{b(q)}|\geq x , so by Lemma 4.19 applied to the entire \mathcal{T}(F) , there are at most 1+\sum_{y=x}^{|F|}2^{|F|-y}=O(2^{|F|-x}) different representatives. Now, observe that ignoring the stepchildren (which are leaves) in \mathcal{T}(F) gives a binary tree of depth \leq d , where the “Branch” nodes are exactly those with two children. Thus, we see that each representative node is chosen by at most 2d nodes, so item 1 follows. For item 2, note that by Lemma 4.19 , the number of “Branch” nodes in \mathcal{T}(F) is at most \sum_{x=0}^{|F|}2^{|F|-x}=O(2^{|F|}) . So the binary tree obtained by deleting the stepchildren has O(d\cdot 2^{|F|}) nodes, and adding back the stepchildren at most doubles this number. ∎ We are now ready to complete the query time analysis. First, the time spent in a node q of \mathcal{T}(F) to identify the relevant case is \tilde{O}(|F|) , as we only need to check the membership of the vertices in F in a constant number of vertex subsets. The rest of the time spent in q is by the query to the cut detector stored at q , which only happens in the “Leaf” or “Trim” cases. In the “Leaf” case, we either query a \mathsf{FewTcutdet} structure constructed for O(f/\epsilon)=O(f\log|T|) terminals, or \mathsf{TEcutdet} structure constructed for a terminal expander with expansion \phi ; this takes at most \tilde{O}(f^{2}/\phi) time (by lemmas 4.4 and 4.3 ). So, by Corollary 4.20 ( 2 ), ignoring the time to query to the cut detectors in the “Trim” nodes, the query takes \tilde{O}(2^{f}\cdot f^{2}/\phi) time. It remains to analyze the ignored time for cut detector queries in “Trim” nodes. In such a node q with |F_{q}|=x , we make a query to a \mathsf{UScutdet} structure which takes \tilde{O}(2^{x}\cdot f) time by Lemma 4.5 . By Corollary 4.20 ( 1 ), summing over all “Trim” nodes, the total time spent is bounded by \sum_{x=0}^{|F|}\tilde{O}(2^{|F|-x})\cdot O(2^{x}\cdot f)=\tilde{O}(2^{|F|}\cdot f^{2}) . All in all, we get that the query F is answered in \tilde{O}(2^{|F|}\cdot f^{2}/\phi) time. Space. The space required for a specific node q in \mathcal{T} is dominated by the cut detector(s) with which q is augmented, which is either \mathsf{FewTcutdet} , \mathsf{TEcutdet} or two \mathsf{UScutdet} s. It is readily verified that the latter case is the heaviest, requiring \tilde{O}(f2^{2f}|V(G_{q})|) space by Lemma 4.5 (recall that |U_{L_{q}}|,|U_{R_{q}}|\leq f+1 ). Summing over all nodes q in \mathcal{T} and using Lemma 4.15 ( 4 ), we get total space of \tilde{O}(f2^{2f}n) for \mathcal{D} . Preprocessing Time. We first address the construction of the f -LR tree \mathcal{T} . The computation at each node q is dominated by applying Lemma 4.13 on G_{q} . Thus, by the near-linear space of \mathcal{T} in Lemma 4.15 ( 4 ), the construction of \mathcal{T} takes \tilde{O}((fnd^{2})^{1+o(1)+O(1/r)}\cdot(\log(fnd^{2}))^{O(r^{4})}/\phi) time. In the construction of \mathcal{D} from \mathcal{T} , the bottleneck is augmenting each node q in \mathcal{T} with its cut detector(s). If q is a leaf, it is augmented either with \mathsf{TEcutdet} or with \mathsf{FewTcutdet} constructed for |E(G_{q})| , which takes |E(G_{q})|^{1+o(1)}/\phi+\tilde{O}(f|E(G_{q})|) time by Lemmas 4.3 and 4.4 . If q is a internal, it is augment with two \mathsf{UScutdet} constructed for its left and right graphs, which are G_{q_{r}} and G_{q_{l}} , where the “U-set” has \leq 2(f+1) vertices. This takes \tilde{O}(f2^{2f}(|E(G_{q_{l}})|+|E(G_{q_{r}})|) time by Lemma 4.5 . Summing over all q and using Lemma 4.15 ( 4 ), we get f^{2}n^{1+o(1)}/\phi+\tilde{O}(f^{2}2^{2f}n) time for constructing \mathcal{D} from \mathcal{T} . So, given any constant \delta>0 , we can set the parameter r in Equation 1 to be a large enough constant (depending only on \delta ), and obtain the running time stated in Theorem 4.2 , except for the extra O(2^{2f}) factor. Alternatively, we can set r=\Theta(\log\log n) , so that the expansion becomes \phi=1/n^{o(1)} , resulting in the preprocessing improvement at cost of n^{o(1)} factors in space and query time stated in Theorem 4.2 (again, except for the extra O(2^{2f}) factor). This nearly concludes the proof of Theorem 4.2 , except for O(2^{2f}) factors appearing the space of preprocessing time; Section 4.7 explains how these can be shaved to get Theorem 4.2 . But, before we get to shaving this factors in the general case, we first provide the details on the f -connected case in the following Section 4.6 . (This is for ease of presentation purposes: the modifications for shaving the O(2^{2f}) factors in the general case are not needed in the f -connected case, so we prefer to defer them.) 4.6 Minimum Vertex Cut Oracles This section is devoted to minimum vertex cuts, that when queried with any F\subseteq V , can determine if F is a minimum vertex cut in G , hence providing a establishing Theorem 1.1 . This oracle is obtained by an improved variant of our f -vertex cut oracle when the given graph G is f -connected. The preprocessing first computes the vertex connectivity f of G , and the space and query time of the resulting oracle also depend on f . We do this by showing the relatively minor modifications to the general f -vertex cut oracle of Theorem 1.2 , which utilize the additional f -connectivity promise to improve space and query time. Specifically, we set our goal to improving the space and query time of the cut detector \mathcal{D} from Theorem 4.2 to \tilde{O}(fn) and \tilde{O}(f^{2}) , respectively; the corresponding complexities of the oracle are only larger by an O(\log n) factor, as discussed in Section 4.1 . Improved Properties of Left/Right Graphs. Let G , T , f and (L,S,R) be as in Section 4.3 , with the corresponding f -left and f -right graphs G_{L} , G_{R} defined there. The structural key for the improvements in the f -connected case lies in the following lemma, which strengthens Lemma 4.9 . This is essentially [ NSY23 , Lemma 3.7] ; we provide the proof to keep the presentation stand-alone. Lemma 4.21 . Suppose G is f -connected. Let F\subseteq V with |F|=f . Suppose that in G , F separates T but does not separate S . Then either: • F\subseteq L\cup S and F separates T\cap V(G_{L}) in G_{L} , or • F\subseteq R\cup S and F separates T\cap V(G_{R}) in G_{R} . Proof. The proof starts exactly as in Lemma 4.9 . Let (A,F,B) be a T -cut in G . Because F does not separate S , we may assume that B\cap S=\emptyset (otherwise A\cap S=\emptyset , so we can swap A and B ). Choose some terminal t^{*}\in B\cap T . Then t^{*}\notin S , hence t^{*}\in L\cup R . In the proof Lemma 4.9 , it is shown that t^{*}\in L implies that F\cap V(G_{L}) separates T\cap V(G_{L}) in G_{L} , and symmetrically for t^{*}\in R . So, all that remains to show is that t^{*}\in L implies F\subseteq L\cup S (and the argument for t^{*}\in R implies F\subseteq R\cup S is symmetric). Consider Z=N(L\cap B) , i.e., Z is the set of vertices outside L\cap B with some neighbor in L\cap B (with respect to the graph G ). Note that Z\cap A=Z\cap R=\emptyset , since there are no edges between A and B , nor between L and R . Thus, Z separates t^{*}\in L\cap B from every vertex in A\cup R\neq\emptyset , so Z is a cut in G . Finally, we claim that Z=F ; this will end the proof as we already saw that Z\cap R=\emptyset . Because Z is a cut in G , and F is a minimum cut in G , it suffices to prove that Z\subseteq F . Let u\in Z . Since Z\cap A=\emptyset , we get u\in F or u\in B ; we show that the latter is impossible. Seeking contradiction, suppose u\in B . Then, since Z=N(L\cap B) , we have that u\notin L . Also, because B\cap S=\emptyset , we get u\notin S . Thus, it must be that u\in R . But, since Z=N(L\cap B) , u has some neighbor in L\cap B\subseteq L , i.e., there is an edge between L and R — contradiction. ∎ Additionally, we observe that f -connectivity is inherited from G by G_{L} and G_{R} , as follows immediately from Lemma 4.10 . Observation 4.22 . If G is f -connected, then so are G_{L} and G_{R} . We now turn to describe the modifications to improve the cut detector \mathcal{D} of Theorem 4.2 constructed in case G is f -connected. Construction of \mathcal{T} and S^{*} . The construction of the f -LR tree \mathcal{T} and the new terminal set S^{*} stays exactly the same as in Section 4.4 . Note that now, by (inductively applying) Observation 4.22 , every graph G_{q} associated with a node q of \mathcal{T} is f -connected. Construction of \mathcal{D} . The only modification we make to \mathcal{D} is in the cut detectors with which we augment the internal nodes of \mathcal{T} . Let q be an internal node in \mathcal{T} , associated with the graph-terminals pair (G_{q},T_{q}) and the cut (L_{q},S_{q},R_{q}) in G_{q} . Recall that previously, in Section 4.5 , we augmented q with two \mathsf{UScutdet} structures, one for G_{L_{q}} and one for G_{R_{q}} , with “S-set” S_{q} and “U-set” U_{L_{q}}\cup U_{R_{q}} . In the f -connected case, this simplifies: we will only need one \mathsf{UScutdet} constructed for G_{q} itself , with the same “S-set”, but with an empty “U-set” . Namely, we augment the internal node q with \mathsf{UScutdet}(G_{q},\emptyset,S_{q},f) . Other than this modification, the construction of \mathcal{D} is exactly as in Section 4.5 . Space. As in Section 4.5 , the space required for a specific node q in \mathcal{T} is dominated by the cut detector with which q is augmented, which is either \mathsf{FewTcutdet} , \mathsf{TEcutdet} or \mathsf{UScutdet} s. Now we only have \mathsf{UScutdet} s with empty “U-set”, so its space improves to O(f|V(G_{q})|) . The space of \mathsf{FewTcutdet} or of \mathsf{TEcutdet} is \tilde{O}(f|V(G_{q})|) , by Lemma 4.4 and Lemma 4.3 . So, summing over all nodes q in \mathcal{T} and using Lemma 4.15 ( 4 ), we now get total space of \tilde{O}(fn) for \mathcal{D} . Query Algorithm for \mathcal{D} . The implementation of the query is recursive, in the same manner described in Section 4.5 . We only consider queries F\subseteq V with |F|=f (as if |F|0 . The last term can be made n^{1+o(1)} by increasing the space and query time by n^{o(1)} factors. Before explaining the slight modifications of the original construction to obtain Lemma 4.25 , we show how it is used to get Theorem 4.2 . First, we define S^{*}=S^{*}_{1}\cup\cdots\cup S^{*}_{k} , so |S^{*}|\leq\frac{1}{2}|T| . Then, the (f,T,S^{*}) -cut detector \mathcal{D} simply consists of \mathcal{D}_{1},\dots,\mathcal{D}_{k} . To answer a query F\subseteq V with |F|\leq f , we query each \mathcal{D}_{i} such that T_{i}\cap F=\emptyset , and return “cut” if one of these queries returned “cut” , or “fail” if all of them returned “fail” . The correctness follows from Corollary 4.24 . To conclude this section, we provide the detailed changes to the original construction for Theorem 4.2 to obtain its modified version in Lemma 4.25 : • First, we need minor alterations in Section 4.3 concerning left and right graphs. In Definition 4.8 , we simplify U_{R} to just contain one arbitrary terminal from R\cap T and change U_{L} in the same fashion. By adding our current assumption that F\cap T=\emptyset , all of the proofs in this section easily adapt to hold (note that there is no point in having f+1 terminals in U_{L} or U_{R} , because now F cannot intersect these sets). • Next, we describe the modifications to the parameters in the construction of the LR-tree ( Section 4.4 ) so as to obtain |S^{*}|\leq\frac{1}{2k}|T| . We reduce \epsilon in Equation 1 to \epsilon:=(ck\log|T|)^{-1} for a large enough constant c>1 . Since k=\tilde{O}(1) , the expansion \phi in Equation 2 remains \phi=1/\operatorname{poly}\log n . The analysis yielding Lemma 4.15 remains true, except we improve the bound for |S^{*}| . First, we derive that |S^{*}|\leq\frac{1}{3}((1+3\epsilon)^{d+1}-1)|T| exactly as before. Observe that (1+3\epsilon)^{d+1}\leq e^{3\epsilon(d+1)}\leq 1+6\epsilon(d+1) (the first inequality is 1+x\leq e^{x} , and the second is e^{z}\leq 1+2z for z\in[0,1] ). So we get |S^{*}|\leq 2\epsilon(d+1)|T|\leq\frac{1}{2k}|T| (the last inequality is since d=O(\log|T|) , so we can set the constant c large enough to make 2\epsilon(d+1)\leq\frac{1}{2k} ). • Finally, we modify the construction of the (f,T,S^{*}) -cut detector \mathcal{D} in Section 4.5 , by changing the U-sets in the US cut detectors to be \emptyset instead of U_{L_{q}}\cup U_{R_{q}} . This eliminates the 2^{2f} factors in space and preprocessing time, as they came from using the original U-sets. This change does not hinder any use of US cut detectors, since now U_{L_{q}}\cup U_{R_{q}}\subseteq T but F\cap T=\emptyset , so whenever we use a US cut detector the query is contained in the S-set. 5 Cut Respecting Terminal Expander Decomposition In this section, we give a clean graph-theoretical characterization that follows as a corollary from the construction of f -LR decomposition trees in Section 4.4 . Informally, it says that any n -vertex graph G can be “decomposed” into a collection of terminal expanders (or graphs with very few terminals), such that the terminal cuts in them jointly capture all vertex cuts in G of size f or less. Further, the total size of all these graphs is rather small, roughly proportional to fn . We call this collection an f -cut respecting terminal-expander decomposition ( f -cut respecting TED for short), formally defined, as follows: Definition 5.1 ( f -Cut Respecting \phi -TED) . Let G=(V,E) be an n -vertex graph, let f\geq 1 be an integer, and let 0<\phi\leq 1 . An f -cut respecting \phi -terminal expander decomposition for G is a collection \mathcal{G}=\{(G_{1},T_{1}),\ldots,(G_{\ell},T_{\ell})\} that satisfies the following: • (Terminal Expanders or Few Terminals) For every (G_{i},T_{i})\in\mathcal{G} , it holds that T_{i}\subseteq V(G_{i})\subseteq V , and G_{i} is either a (T_{i},\phi) -terminal expander, or |T_{i}|=\tilde{O}(f) . • (Soundness) For every G_{i} , every vertex cut F in G_{i} with |F|\leq f is also a cut in G . • (Completeness) For every vertex cut F in G with |F|\leq f or less, there exists some G_{i} such that F\cap V(G_{i}) separates the terminals T_{i} in G_{i} . • (Lightness) \sum_{i}|V(G_{i})|=\widetilde{O}(n) and \sum_{i}|E(G_{i})|=\widetilde{O}(fn) . The following theorem essentially follows from the f -LR tree construction: Theorem 5.2 . For any f\geq 1 , every n -vertex graph G admits an f -cut respecting \phi -TED with \phi=1/\operatorname{poly}\log n that can be computed deterministically in polynomial time, or with smaller \phi=1/n^{o(1)} but improved running time of O(m)+fn^{1+o(1)} . Proof sketch. As detailed in Section 4.4 , the computation of the f -LR tree for G in fact outputs a pair (\mathcal{T},S^{*}) where \mathcal{T} is the tree itself, and S^{*} is the union of all separators S_{q} from the vertex cuts in the associated graphs of each node q in \mathcal{T} . Consider the collection of pairs (G_{q},T_{q}) associated with the leaves of \mathcal{T} . This collection satisfies the first and last conditions in Definition 5.1 , according to Lemma 4.15 , properties 1 and 4 . (Recall that the expansion \phi is determined by setting the parameter r , see Equations 1 and 2 . Letting r=O(1) gives \phi=1/\operatorname{poly}\log n , and r=\Theta(\log\log n) gives \phi=1/n^{o(1)} , which determines the construction time of (\mathcal{T},S^{*}) as explained in the preprocessing time analysis in Section 4.5 .) Further, by inductively using the soundness and completeness properties of f -left and f -right graphs ( Lemma 4.9 and Lemma 4.10 ), one can show that the collection of pairs (G_{q},T_{q}) associated with the leaves of \mathcal{T} fully guarantee the soundness condition of Definition 5.1 , and partially guarantee the completeness condition, i.e., guarantee it only when F separates T but not S^{*} in G . (The proof is very similar in essence to the proof of Lemma 4.18 , only easier as one does not need to do deal with “trim” cases.) This last issue is resolved in a similar manner to the construction of cut oracles from terminal cut detectors explained in Section 4.1 . We initialize T_{1}=V , and continue in iterations i=1,2,\dots . In iteration i , we halt if T_{i}\neq\emptyset , and otherwise apply the f -LR tree construction for (G,T_{i}) which yields a pair (\mathcal{T}_{i},S^{*}_{i}) with |S^{*}_{i}|\leq\frac{1}{2}|T_{i}| (by Lemma 4.15 , Property 3 ), and set T_{i+1}:=S^{*} . Thus, this process can only continue for O(\log n) iterations. We take the collection of all pairs (G_{q},T_{q}) associated in the leaves of all of the O(\log n) constructed f -LR trees. By essentially the same arguments as in Section 4.1 (in the proof of Theorem 4.2 ), this collection fully gauntness the completeness property of Definition 5.1 . The other properties still hold; the lightness and running time only incur an O(\log n) factor. ∎ 6 Space Lower Bound for Vertex Cut Oracles In this section, we show the space lower bound for f -vertex cut oracles on n -vertex graphs of Theorem 1.3 . We start with the more interesting case: The case 2\leq f\leq n/4 . Let U=\{u_{1},\dots,u_{n/2}\} and W=\{w_{1},\dots,w_{n/2}\} . Consider the following process for generating the edge set E of an n -vertex graph with vertex set V=U\cup W : 1. Add a clique on W . 2. Choose n/2 distinct subsets F_{1},\dots,F_{n/2}\subseteq W , each of size |F_{i}|=f . Denote the collection of chosen subsets by \mathcal{F}=\{F_{1},\dots,F_{n/2}\} 3. For each i=1,\dots,n/2 , add edges between u_{i} and every vertex in F_{i} . Note that any graph G generated by this process is f -connected: if one deletes less than f vertices from G , then every surviving vertex from U must have some surviving neighbor in W , and the vertices of W are connected by a clique. Let G^{0} and G^{1} be two graphs generated by the above process, whose corresponding collections \mathcal{F}^{0}=\{F^{0}_{1},\dots,F^{0}_{n/2}\} and \mathcal{F}^{1}=\{F^{1}_{1},\dots,F^{1}_{n/2}\} chosen in step 2 are different. Let \mathcal{O}^{0} and \mathcal{O}^{1} be f -vertex cut oracles built for G^{0} and G^{1} respectively. Because \mathcal{F}^{0}\neq\mathcal{F}^{1} , there must be some F\subseteq W of size |F|=f which belongs to exactly one of the collections \mathcal{F}^{0},\mathcal{F}^{1} . Assume without loss of generality that F\in\mathcal{F}^{0} and F\notin\mathcal{F}^{1} . We show that on query F , the oracle \mathcal{O}^{0} returns “cut” , while oracle \mathcal{O}^{1} returns “not a cut” , so these two oracles must be different. • Oracle \mathcal{O}^{0} : As F\in\mathcal{F}^{0} , we have F=F^{0}_{i} for some 1\leq i\leq n/2 . So in G^{0} , the neighbor set of u_{i} is F , and thus u_{i} is an isolated vertex in G^{0}-F , meaning F is a cut in G^{0} , so the oracle \mathcal{O}^{0} must return “cut” . • Oracle \mathcal{O}^{1} : Consider some u_{i}\in U . As F\notin\mathcal{F}^{1} , we have F\neq F^{1}_{i} . Since |F|=|F^{1}_{i}|=f , there must be some w\in F^{1}_{i}-F . This w\in W is a neighbor of u_{i} in G^{1}-F . So, we have shown that in G^{1}-F , every vertex in U has some neighbor in W . As G^{1}[W] is a clique, this implies that G^{1}-F is connected, so F is not a cut in G^{1} and the oracle \mathcal{O}^{1} must return “not a cut” . We are now ready to derive the space lower bound. Let \mathscr{C} be the set consisting of all possible choices of \mathcal{F} in step 2, that is \mathscr{C}=\left\{\{F_{1},\dots,F_{n/2}\}\mid\text{$F_{1},\dots,F_{n/2}$ are distinct subsets of $W$, each of size $f$}\right\} As we just showed, each \mathcal{F}\in\mathscr{C} gives rise to a different f -vertex cut oracle on some n -vertex graph. Thus, in the worst case, the bit representation of such an oracle must consume \Omega(\log|\mathscr{C}|) bits. So, all that remains is to bound |\mathscr{C}| from below. We have |\mathscr{C}|=\binom{\binom{|W|}{f}}{n/2}, as there are \binom{|W|}{f} different subsets of W of size f , and each element in \mathscr{C} is formed by choosing n/2 of those subsets. Now, \binom{|W|}{f}\geq\left(\frac{|W|}{f}\right)^{f}=2^{f(\log|W|-\log(f))}=2^{f\log(\frac{n}{2f})} (the inequality is \binom{k}{r}\geq\left(\frac{k}{r}\right)^{r} for every 1\leq r\leq k ). So, we get |\mathscr{C}|=\binom{\binom{|W|}{f}}{n/2}\geq\left(\frac{\binom{|W|}{f}}{n/2}\right)^{n/2}\geq\left(\frac{2^{f\log(\frac{n}{2f})}}{n/2}\right)^{n/2}\\ =2^{\frac{n}{2}\left(f\log(\frac{n}{2f})-\log(\frac{n}{2})\right)} (the first inequality is \binom{k}{r}\geq\left(\frac{k}{r}\right)^{r} once again), and taking logarithms yields \log|\mathscr{C}|\geq\frac{fn}{2}\left(\log\big(\frac{n}{2f}\big)-\frac{1}{f}\log\big(\frac{n}{2}\big)\right). Recall that 2\leq f\leq n/4 . We split this range into two intervals and analyze them separately: • If \big(\frac{n}{2}\big)^{1/10}\leq f\leq\frac{n}{4} , then \frac{1}{f}\log\big(\frac{n}{2}\big)=o(1) while \log\big(\frac{n}{2f}\big)\geq 1 , so we get \log|\mathscr{C}|=\Omega(fn\log(n/f)) . • If 2\leq f\leq\big(\frac{n}{2}\big)^{1/10} , then we have \log\big(\frac{n}{2f}\big)-\frac{1}{f}\log\big(\frac{n}{2}\big)\geq\left(\frac{9}{10}-\frac{1}{f}\right)\log\big(\frac{n}{2}\big)\geq 0.4\log\big(\frac{n}{2}\big) , so again we get \log|\mathscr{C}|=\Omega(fn\log(n/f)) . So anyway, we get a space lower bound of \Omega(\log|\mathscr{C}|)=\Omega\Big(fn\cdot\log\big(\frac{n}{f}\big)\Big). The Case f=1 . This case is much easier. Consider a path P=(v_{1},\dots,v_{n}) . Suppose we generate a new graph from P by making \Omega(n) binary choices: for every integer 1\leq k0 there is some k=k(\varepsilon)\geq 3 such that k -SAT with N variables cannot be solved in O(2^{(1-\varepsilon)N}) time. As many SETH-based lower bounds, the lower bound actually relies on the SETH-hardness of the Orthogonal Vectors (OV) problem: given two sets of binary d -dimensional vectors A,B\subseteq\{0,1\}^{d} with |A|=|B|=n , determine if there exists some a\in A and b\in B such that \sum_{i=1}^{d}a_{i}\cdot b_{i}=0 . Williams [ Wil05 ] showed that SETH implies the Orthogonal Vectors Hypothesis (OVH) : Conjecture A.2 (Orthogonal Vectors Hypothesis (OVH)) . For every \varepsilon>0 there is some c=c(\varepsilon)>0 such that OV with dimension d=c\log n cannot be solved in O(n^{2-\varepsilon}) time. We now give the conditional lower bound: Theorem A.1 (Slight Adaptation of [ LS22a , Theorem 8.9] ) . Assuming OVH, for every \varepsilon>0 there is c=c(\epsilon)>0 such that, for f=c\log n , there is no f -vertex cut oracle for n -vertex graphs with preprocessing time O(n^{2-\varepsilon}) and query time O(n^{1-\varepsilon}) . Proof. Fix \epsilon>0 , and let c=c(\varepsilon)>0 be the corresponding constant guaranteed by OVH. Suppose towards contradiction that there is an f -vertex cut oracle for n -vertex graphs with preprocessing time O(n^{2-\varepsilon}) and query time O(n^{1-\varepsilon}) . We will use this f -vertex cut oracle to solve any OV instance A,B\subseteq\{0,1\}^{f} with |A|=|B|=n . We construct a graph G=(V,E) with n+f+1=O(n) vertices, which is defined only by A : \displaystyle V \displaystyle=\{x_{a}\mid a\in A\}\cup\{y_{i}\mid 1\leq i\leq f\}\cup\{z\} \displaystyle E \displaystyle=\big\{(x_{a},y_{i})\mid\text{$a\in A$, $1\leq i\leq f$ and $a_{i}=1$}\big\}\cup\{(y_{i},z)\mid 1\leq i\leq f\}. For every b\in B , we define F_{b}=\{y_{i}\mid b_{i}=0\} . We claim that there is some a\in A orthogonal to b iff G-F_{b} is disconnected. If a\in A is orthogonal to b , then b_{i}=0 whenever a_{i}=1 , meaning that y_{i}\in F_{b} whenever y_{i} is a neighbor of x_{a} , so x_{a} is isolated in G-F_{b} . Conversely, if G-F_{b} is disconnected, then some x_{a} must be disconnected from z , so each of its neighbors y_{i} must belong to F_{b} . Thus, a_{i}=1 could only happen when b_{i}=0 , so a and b are orthogonal. In light of the above claim, we can solve the OV instance by constructing an f -vertex cut oracle for G , and querying it with F_{b} for every b\in B , which takes O(n^{2-\varepsilon}) time for oracle construction, and n\cdot O(n^{1-\varepsilon}) time for the queries, hence O(n^{2-\varepsilon}) time in total — contradiction to OVH. (Note that constructing G itself takes only O(fn)=O(n\log n) time.) ∎ (ii) Polynomial Number of Faults. Next, we consider the regime where f=\Theta(n^{\alpha}) for some absolute constant \alpha\in(0,1) . For this regime, we state a plausible online version of OVH, which can be seen as the natural “OV analog” of the popular OMv conjecture [ HKNS15 ] . Assuming this online OVH version, in this regime one cannot get query time polynomially smaller than O(fn) . Formally, consider the following Online Orthogonal Vectors (Online OV) problem: Initially, one is given a set A of size n , consisting of binary d -dimensional vectors, and can preprocess them. Then, n queries b^{(1)},\dots,b^{(n)}\in\{0,1\}^{d} arrive one by one, and for each b^{(j)} it is required to determine if there is some a\in A such that \sum_{i=1}^{d}a_{i}\cdot b^{(j)}_{i}=0 (before the next query arrives). Conjecture A.3 (Online OVH [ Abb25 ] ) . Let \alpha>0 be a constant. For every constant \varepsilon>0 , there is no algorithm that solves Online OV with dimension d=\Theta(n^{\alpha}) with \operatorname{poly}(n) preprocessing time and amortized query time O(n^{1+\alpha-\varepsilon}) . We note that in the standard offline setting, the only known way to break this bound is via fast matrix multiplication, which (as conjectured by OMv) does not apply to the online setting [ Abb25 ] . An identical construction as in the proof of Theorem A.1 now yields: Theorem A.2 . Assuming Conjecture A.3 , for every constant \alpha\in(0,1) and constant \varepsilon>0 , letting f=\Theta(n^{\alpha}) , there is no f -vertex cut oracles for n -vertex graphs where with \operatorname{poly}(n) preprocessing time and O((fn)^{1-\epsilon}) query time. (iii) Linear Number of Faults. Finally, in the regime f=\Omega(n) , one can actually show the same lower bound as above assuming the more standard OMv conjecture. The construction is actually based on the OuMv conjecture , which was shown to follow from the OMv conjecture in [ HKNS15 ] , so we only define the former here. In the OuMv problem, one is initially given an integer n and an n\times n Boolean matrix M . Then, \operatorname{poly}(n) many queries arrive. Each query consists of two vectors u,v\in{0,1}^{n} , and asks for u^{T}Mv ; the output must be produced before the next query is revealed. Conjecture A.4 (OuMv Conjecture [ HKNS15 ] ) . For any constant \epsilon>0 , there is no algorithm that solving OuMv correctly with probability at least 2/3 such that the preprocessing time is polynomial on n and the amortized query time is O(n^{2-\epsilon}) . Theorem A.3 . Assuming OMv conjecture, for every \epsilon>0 , letting f=\Omega(n) , there is no f -vertex cut oracle for n -vertex graphs with preprocessing time polynomial on n and query time O(n^{2-\epsilon}) . Proof. The proof is based on [ LS22a , Theorem 8.6] . Given the n\times n input matrix M , we construct a graph G=(V,E) with \displaystyle V \displaystyle=\{a_{1},\dots,a_{n},b_{1},\dots b_{n}\} \displaystyle E \displaystyle=\{(a_{i},b_{j})\in A\times B\mid M_{i,j}=1\}\cup\{(a_{i},a_{j})\mid 1\leq i0 and k\in\mathbb{N} , there exists a constant c=c(\epsilon_{s},k) such that any k -SAT formula F with N variables can be expressed as \Phi=\bigvee_{i=1}^{\ell}\Phi_{i} , where \ell=O\left(2^{\epsilon_{s}N}\right) , and each \Phi_{i} is a k -SAT formula with at most cN clauses. Moreover, this disjunction can be computed in time O\left(2^{\epsilon_{s}N}\operatorname{poly}(N)\right) . Algorithm. We use the sparsification lemma Lemma B.4 with \epsilon_{s}=\frac{\epsilon}{6t} to get \ell=O\left(2^{\epsilon_{s}N}\right) formulas, each has c(\epsilon_{s},k)\cdot N many clauses. It suffices to check if there exists an assignment such that one of these formulas can be satisfied. Now, we focus on one of these formulas. Suppose the variable set is \mathcal{U} and the formula has the clause set \mathcal{C} where |\mathcal{C}|=c(\epsilon_{s},k)\cdot N . Let \mathcal{U}^{\prime}\subseteq\mathcal{U} be an arbitrary subset of variables of size \delta N where \delta:=\frac{1}{2t} . Split the clause set \mathcal{C} to f:=\frac{c(\epsilon_{s},k)}{\delta} many clause sets, each of size \delta N . Denote them as \mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}...\cup\mathcal{C}_{f} . Construct a graph G with vertex set V=2^{\mathcal{U}^{\prime}}\cup\left(\bigcup_{i\in[f]}2^{\mathcal{C}_{i}}\right). Each vertex in U\in 2^{\mathcal{U}^{\prime}} represents a truth assignment to the variables in \mathcal{U}^{\prime} (variables in U are set to ‘true’, and the remaining variables \mathcal{U}^{\prime}-U are set to ‘false’). Each vertex in 2^{\mathcal{C}_{i}} represents a clause subset of \mathcal{C}_{i} . The edge set E of G is defined as follows. For every assignment U\in 2^{\mathcal{U}^{\prime}} and for every i\in[f],C\in 2^{\mathcal{C}_{i}} , connect an edge from U to C iff at least one clause in C is not satisfied by U . Moreover, the edge set E contains edges forming a clique on \cup_{i\in[f]}2^{\mathcal{C}_{i}} . We initialize the oracle \mathcal{O} on G with the switched off vertices being F:=\bigcup_{i\in[f]}2^{\mathcal{C}_{i}}. For every assignment U^{\prime}\subseteq\mathcal{U}-\mathcal{U}^{\prime} to the variables outside \mathcal{U}^{\prime} , let \mathcal{C}_{i,U^{\prime}} be the subset of clauses in \mathcal{C}_{i} that are not satisfied by U^{\prime} . Notice that \mathcal{C}_{i,U^{\prime}} is a vertex in 2^{\mathcal{C}_{i}} . We make a query using \mathcal{O} with F_{\mathrm{on}}:=\{\mathcal{C}_{i,U^{\prime}}\mid i\in[f]\}. If one of these queries corresponding to some U^{\prime}\subseteq\mathcal{U}-\mathcal{U}^{\prime} returns ‘not connected’, then we return ‘can satisfy’. Otherwise, we return ‘cannot satisfy’. Correctness. For the first direction, suppose there exists an assignment U^{*}\subseteq\mathcal{U} satisfying one of these sparsified k -SATs. Let U^{*}_{1}\subseteq\mathcal{U}^{\prime} be the assignment restricted to \mathcal{U}^{\prime} and U^{*}_{2}\subseteq\mathcal{U}-\mathcal{U}^{\prime} be the assignment restricted to \mathcal{U}-\mathcal{U}^{\prime} . Consider the query corresponding to U^{*}_{2} . Remember that \mathcal{C}_{i,U^{*}_{2}} are the clauses in \mathcal{C}_{i} that are not satisfied by U^{*}_{2} . Since U^{*}=U^{*}_{1}\cup U^{*}_{2} satisfies all clauses, it must be that U^{*}_{1} satisfies all clauses in \mathcal{C}_{i,U^{*}_{2}} . According to the definition of the edge set, there is no edge from U^{*}_{1} to \mathcal{C}_{i,U^{*}_{2}} for every i\in[f] . Thus, U^{*}_{1} becomes a singleton vertex, so the graph G[(V-F)\cup F_{\mathrm{on}}] is not connected on the query F_{\mathrm{on}}=\{\mathcal{C}_{i,U^{*}_{2}}\mid i\in[f]\} . In the other direction, suppose the algorithm returns ‘can satisfy’. It means that for a query that corresponds to some assignment U^{\prime}\subseteq\mathcal{U}-\mathcal{U}^{\prime} , the graph is not connected. Remember that \bigcup_{i\in[f]}2^{\mathcal{C}_{i}} is a clique, hence so are the ‘turned-on’ vertices F_{\mathrm{on}}=\{\mathcal{C}_{i,U^{\prime}}\mid i\in[f]\} . Thus, if every vertex in 2^{\mathcal{U}^{\prime}} is connected to F_{\mathrm{on}} , the graph G[(V-F)\cup F_{\mathrm{on}}] is connected. So there must be a vertex U\in 2^{\mathcal{U}^{\prime}} such that U has no edge to F_{\mathrm{on}} . According to the definition of edge set, this means that U satisfies all clauses in \mathcal{C}_{i,U^{\prime}} for every i\in[f] . Moreover, U^{\prime} satisfies all clauses in \mathcal{C}_{i}-\mathcal{C}_{i,U^{\prime}} according to the definition. Thus, U\cup U^{\prime} satisfies all clauses in \mathcal{C}_{i} for every i\in[f] , so \mathcal{C} can be satisfied. Running time. For convenience, we use O^{*}(\cdot) to hide polynomial factors on N . The sparsification lemma Lemma B.4 takes time O^{*}(2^{\epsilon_{s}N}) . Then we get \ell formulas, and we solve each formula independently; the final running time should be multiplied by \ell=O(2^{\epsilon_{s}N}) . For each formula, we construct a graph with number of vertices n=2^{\delta N}+f\cdot 2^{\delta N}=O(2^{\delta N}) and at most and number of edges at most m\leq n^{2}=O(2^{2\delta N}). Notice that each edge can be checked in at most polynomial time on N . Then, we initialize \mathcal{O} on the graph G , which takes a preprocessing time of n^{t}\leq O(2^{t\delta N})\leq O(2^{N/2}). Then, for each subset of \mathcal{U}-\mathcal{U}^{\prime} we do a query. The number of queries is 2^{(1-\delta)N} , each query takes time O(n^{1-\epsilon})=O(2^{\delta(1-\epsilon)N}) . We thus bound the total running time by O^{*}\left(2^{\epsilon_{s}N}+2^{\epsilon_{s}N}\cdot\left(2^{2\delta N}+\underbrace{2^{N/2}+2^{(1-\delta)N}\cdot 2^{\delta(1-\epsilon)N}}_{\text{data structure }}\right)\right). Plugging in \epsilon_{s}=\epsilon/6t,\delta=1/2t,\epsilon_{t}=\epsilon/4t , the running time is O^{*}\left(2^{\left(1-\frac{\epsilon}{3t}\right)N}\right)\leq o(2^{(1-\epsilon_{t})N}) which violates SETH ( Conjecture A.1 ). Notice that f is defined as f=\frac{c(\epsilon_{s},k)}{\delta}=\frac{c(\epsilon/6t,k(\epsilon/4t))}{1/2t}, which is a constant depending on \epsilon,t (recall that c and k are the fixed functions in A.1 and B.4 ). ∎