Full metadata record
DC FieldValueLanguage
dc.contributor.authorChang, Yi-Junen_US
dc.contributor.authorFarach-Colton, Martinen_US
dc.contributor.authorHsu, Tsan-Shengen_US
dc.contributor.authorTsai, Meng-Tsungen_US
dc.date.accessioned2020-05-05T00:01:58Z-
dc.date.available2020-05-05T00:01:58Z-
dc.date.issued2020-01-01en_US
dc.identifier.isbn978-3-95977-140-5en_US
dc.identifier.issn1868-8969en_US
dc.identifier.urihttp://dx.doi.org/10.4230/LIPIcs.STACS.2020.34en_US
dc.identifier.urihttp://hdl.handle.net/11536/154032-
dc.description.abstractThe semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an n-node input graph to be read sequentially in p passes using (O) over tilde (n) space. If the list of edges includes deletions, then the model is called the turnstile model; otherwise it is called the insertion-only model. In both models, some graph problems, such as spanning trees, k-connectivity, densest subgraph, degeneracy, cut-sparsifier, and (Delta + 1)-coloring, can be exactly solved or (1 + epsilon)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require (Omega) over tilde (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 maximum-leaf spanning trees. Our results, in both the insertion-only and the turnstile models, are as follows. Maximum-Leaf Spanning Trees: This problem is known to be APX-complete with inapproximability constant rho is an element of [245/244,2). By constructing an epsilon-MLST sparsifier, we show that for every constant epsilon > 0, MLST can be approximated in a single pass to within a factor of 1 + epsilon w.h.p. (albeit in super-polynomial time for epsilon <= p - 1 assuming P not equal NP) and can be approximated in polynomial time in a single pass to within a factor of rho(n) + epsilon w.h.p., where rho(n) is the supremum constant that MLST cannot be approximated to within using polynomial time and (O) over tilde (n) space. In the insertion-only model, these algorithms can be deterministic. BFS Trees: It is known that BFS trees require w(1) passes to compute, but the naive approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(root n), and it offers a smooth tradeoff between pass complexity and space usage. This gives a polynomial separation between single-source and all-pairs 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 (O) over tilde (h) passes, where h is the height of computed DFS trees. Note that h can be as large as Omega(m,/n) for n-node m-edge graphs. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for k-node-connectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(root n), and it also offers a smooth tradeoff between pass complexity and space usage.en_US
dc.language.isoen_USen_US
dc.subjectMax-Leaf Spanning Treesen_US
dc.subjectBFS Treesen_US
dc.subjectDFS Treesen_US
dc.titleStreaming Complexity of Spanning Tree Computationen_US
dc.typeProceedings Paperen_US
dc.identifier.doi10.4230/LIPIcs.STACS.2020.34en_US
dc.identifier.journal37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020)en_US
dc.citation.volume154en_US
dc.citation.spage0en_US
dc.citation.epage0en_US
dc.contributor.department交大名義發表zh_TW
dc.contributor.departmentNational Chiao Tung Universityen_US
dc.identifier.wosnumberWOS:000521377300034en_US
dc.citation.woscount0en_US
Appears in Collections:Conferences Paper