Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate

Ho-Lin Chen, Tsun-Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai · 2026

Read Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate by Ho-Lin Chen, Tsun-Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-12668.txt.

Introduction

Computing a sparse subgraph of a directed graph that proves connectivity is central to streaming and distributed graph methods. Ho-Lin Chen led this work with three co-authors, studying space cost of that job in terms of independence number. A k-node strong connectivity certificate is a subgraph H. For every pair of distinct nodes s and t, the count of pairwise internally node-disjoint paths from s to t in H is at least k. Otherwise it matches the count in the original graph.

Prior work focused on narrow graph classes, since directed connectivity problems are hard in general. This paper gives space bounds for certificates in graphs of bounded independence number, in both streaming and distributed models, with matching upper and lower bounds in key regimes. Results show independence number is a useful gauge for taming directed connectivity certification.

Catalog record

CREATORHo-Lin Chen, Tsun-Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-12668

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate Ho-Lin Chen, Tsun-Ming Cheung, Peng-Ting Lin, Meng-Tsung Tsai Abstract We study the space complexity of computing a sparse subgraph of a directed graph that certifies connectivity in the streaming and distributed models. Formally, for a directed graph G = ( V , A ) G=(V,A) and k ∈ ℕ k\in\mathbb{N} , a k k -node (resp. k k -arc) strong connectivity certificate is a subgraph H = ( V , A ′ ) ⊆ G H=(V,A^{\prime})\subseteq G such that for every pair of distinct nodes s , t ∈ V s,t\in V , the number of pairwise internally node-disjoint (resp. pairwise arc distjoint) paths from s s to t t in H H is at least k k or the corresponding number in G G . Similar notions for undirected graphs have been studied extensively in various streaming models (Cheriyan et al. [SIAM J. Comput. 1993]; Sun and Woodruff [APPROX/RANDOM 2015]; Ahn et al. [SODA 2012]; Assadi and Shah [SOSA 2023]) with several efficient algorithms known. In contrast, streaming algorithms for directed connectivity are scarce due to the inherent hardness of directed connectivity problems: even s s – t t reachability for a single pair ( s , t ) (s,t) in a digraph has a high space lower bound in standard streaming models. Consequently, any streaming algorithm for strong connectivity certificates would inherit these lower bounds for general graphs. In light of the inherent hardness of directed connectivity problems, several prior work focused on restricted graph classes, showing that several problems that are hard in general become efficiently solvable when the input graph is a tournament (i.e., a directed complete graph) (Chakrabarti et al. [SODA 2020]; Baweja, Jia, and Woddruff [ITCS 2022]), or close to a tournament in edit distance (Ghosh and Kuchlous [ESA 2024]). Extending this line of work, our main result shows, at a qualitative level, that the streaming complexity of computing strong connectivity certificates and related directed connectivity problems is parameterized by the independence number of the input graph, demonstrating a continuum of hardness for directed graph connectivity problems. Moreover, our parameterization by independence number, an extrinsic graph parameter not inherent to connectivity problems, appears novel in the streaming context. Quantitatively, for an n n -node graph with independence number α \alpha , we give p p -pass randomized algorithms that compute a k k -node or k k -arc strong connectivity certificate of size O ⁡ ( α ​ n ) O(\alpha n) using O ~ ​ ( k 1 − 1 / p ​ α ​ n 1 + 1 / p ) \tilde{O}(k^{1-1/p}\alpha n^{1+1/p}) space in the insertion-only model, and O ~ ​ ( k 1 − O ⁡ ( 1 / p ) ​ α ​ n 1 + O ⁡ ( 1 / p ) ) \tilde{O}(k^{1-O(1/\sqrt{p})}\alpha n^{1+O(1/\sqrt{p})}) space in the turnstile model. In particular, the algorithm can be made deterministic for k = 1 k=1 with the same pass and space usage in both models. For the lower bound, we show that even when k = 1 k=1 , any p p -pass streaming algorithm for a 1-node or 1-arc strong connectivity certificate in the insertion-only model requires Ω ⁡ ( α ​ n / p ) \Omega(\alpha n/p) space, which immediately implies the same bounds for all larger k k and in the turnstile model. To derive these lower bounds, we introduce the gadget-embedding tournament framework to construct direct-sum-type hard instances with a prescribed independence number, which is applicable to lower-bounding a wide range of directed graph problems. Finally, in the distributed setting, we present protocols for computing directed strong connectivity certificates and strongly connected component (SCC) decompositions, with round complexity parameterized by the independence number. 1 Introduction We study sparse certificates for directed graph connectivity in streaming models. All graphs throughout this paper are simple unless stated otherwise. There are two notions of connectivity in graphs, namely node-connectivity and arc-connectivity , which in turn lead to two corresponding types of connectivity certificates. For any digraph G=(V,A) and a pair of distinct nodes s,t\in V , let \kappa_{st}(G) (resp. \lambda_{st}(G) ) be the maximum number of pairwise internally node-disjoint paths (resp. pairwise arc-disjoint paths) from s to t . A k -node (resp. k -arc) strong connectivity certificate of a digraph G=(V,A) is defined to be a subgraph H=(V,A^{\prime}) of G with A^{\prime}\subseteq A such that for all pairs of distinct nodes s,t\in V \kappa_{st}(H)\geq\min\{k,\kappa_{st}(G)\}\qquad\mbox{ (resp. }\lambda_{st}(H)\geq\min\{k,\lambda_{st}(G)\}\mbox{)}. When k=1 , the notions of 1 -arc and 1 -node strong connectivity certificate coincide, however this equivalence does not hold for k\geq 2 . The notion of strong connectivity certificates was first introduced by Nagamochi and Ibaraki [ 55 ] for undirected graphs, and various notions of connectivity certificates for undirected graphs have been broadly studied in the annotated model [ 37 ] , turnstile model [ 2 , 38 , 4 ] and insertion-only model [ 16 , 25 , 63 ] . Directed connectivity certificates support a broader range of applications since computing an undirected certificate is reducible to computing a directed one. The k -arc strong connectivity certificate enables efficient topological sorting, identification of strongly connected components, and applications to other computational problems, such as computing a minimum chain cover, finding an approximately minimum spanning strong subgraph, identifying k arc-disjoint out-branchings, and detecting strong bridges. The k -node strong connectivity certificate, on the other hand, allows us to test k -connectivity directly and to identify small node cuts and balanced separators. These applications will be discussed in detail in Sections 1.2 and 6 . While directed certificates enable more applications than their undirected counterparts, obtaining them in the streaming model is significantly harder. It is known that s – t reachability problem in a digraph, where we are given distinct nodes s,t\in V and must decide whether there is a directed path from s to t , requires \Omega(n^{2-o(1)}) space [1] [1] [1] Following standard streaming conventions (e.g. [ 3 , 13 , 19 ] ), we measure space lower bounds in bits and space upper bounds in words, with each word consisting of O(\log n) bits. for any o(\sqrt{\log n}) -pass streaming algorithm [ 15 ] . Since G contains a directed path from s to t if and only if \lambda_{st}(G)\geq 1 or, equivalently, \kappa_{st}(G)\geq 1 . It follows that, for any k\geq 1 , computing a k -arc or a k -node strong connectivity certificate inherits the lower bound of the reachability problem. In contrast, for digraphs with independence number at most \alpha , Chen, Lin, and Tsai [ 14 ] showed that a 1 -arc strong connectivity certificate can be obtained via the O(1/\varepsilon) -pass O(\alpha n^{1+\varepsilon}) -space algorithm for any \varepsilon>0 in the insertion-only streaming model. Crucially, this parameterized upper bound [ 14 ] aligns with the observation that in many previous hardness results [ 15 , 39 , 8 , 12 ] , the hard instances are layered graphs, which have linear independence number. More broadly, there has been an emerging literature in studying graph streaming problems on restricted classes of digraphs. One notable class of digraphs that has received considerable attention recently is

Read the complete text