Abstract
The semistreaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an nnode input graph to be read sequentially in p passes using Õ(n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertiononly model. In both models, some graph problems, such as spanning trees, kconnectivity, densest subgraph, degeneracy, cutsparsifier, and (Δ+1)coloring, can be exactly solved or (1+ε)approximated in a single pass; while other graph problems, such as triangle detection and unweighted allpairs shortest paths, are known to require Ω̃(n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees, including BFS, DFS, and maximumleaf spanning trees.
Our results, in both the insertiononly and the turnstile models, are as follows.
 MaximumLeaf Spanning Trees: This problem is known to be APXcomplete with inapproximability constant ρ ∈ [245/244, 2). By constructing an εMLST sparsifier, we show that for every constant ε > 0, MLST can be approximated in a single pass to within a factor of 1+ε w.h.p. (albeit in superpolynomial time for ε ≤ ρ1 assuming P ≠ NP) and can be approximated in polynomial time in a single pass to within a factor of ρ_n+ε w.h.p., where ρ_n is the supremum constant that MLST cannot be approximated to within using polynomial time and Õ(n) space. In the insertiononly model, these algorithms can be deterministic.
 BFS Trees: It is known that BFS trees require ω(1) passes to compute, but the naïve approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(√n), and it offers a smooth tradeoff between pass complexity and space usage. This gives a polynomial separation between singlesource and allpairs shortest paths for unweighted graphs.
 DFS Trees: It is unknown whether DFS trees require more than one pass. The current best algorithm by Khan and Mehta [STACS 2019] takes Õ(h) passes, where h is the height of computed DFS trees. Note that h can be as large as Ω(m/n) for nnode medge graphs. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for knodeconnectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(√n), and it also offers a smooth tradeoff between pass complexity and space usage.
BibTeX  Entry
@InProceedings{chang_et_al:LIPIcs:2020:11895,
author = {YiJun Chang and Mart{\'\i}n FarachColton and TsanSheng Hsu and MengTsung Tsai},
title = {{Streaming Complexity of Spanning Tree Computation}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {34:134:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11895},
URN = {urn:nbn:de:0030drops118951},
doi = {10.4230/LIPIcs.STACS.2020.34},
annote = {Keywords: MaxLeaf Spanning Trees, BFS Trees, DFS Trees}
}
Keywords: 

MaxLeaf Spanning Trees, BFS Trees, DFS Trees 
Collection: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 
Issue Date: 

2020 
Date of publication: 

04.03.2020 