Show simple item record

dc.contributor.author
Chang, Yi-Jun
dc.contributor.author
Farach-Colton, Martin
dc.contributor.author
Hsu, Tsan-Sheng
dc.contributor.author
Tsai, Meng-Tsung
dc.contributor.editor
Paul, Christophe
dc.contributor.editor
Bläser, Markus
dc.date.accessioned
2020-03-30T06:41:28Z
dc.date.available
2020-03-30T04:03:58Z
dc.date.available
2020-03-30T06:41:28Z
dc.date.issued
2020
dc.identifier.isbn
978-3-95977-140-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.STACS.2020.34
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/407124
dc.identifier.doi
10.3929/ethz-b-000407124
dc.description.abstract
The 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 Õ(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 (Δ+1)-coloring, can be exactly solved or (1+ε)-approximated in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs 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 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 ρ ∈ [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 super-polynomial 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 insertion-only 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 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 Õ(h) passes, where h is the height of computed DFS trees. Note that h can be as large as Ω(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(√n), and it also offers a smooth tradeoff between pass complexity and space usage.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl-Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Max-Leaf Spanning Trees
en_US
dc.subject
BFS Trees
en_US
dc.subject
DFS Trees
en_US
dc.title
Streaming Complexity of Spanning Tree Computation
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
154
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
34
en_US
ethz.size
19 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
en_US
ethz.event.location
Montpellier, France
en_US
ethz.event.date
March 10-13, 2020
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2020-03-30T04:04:04Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2020-03-30T06:41:38Z
ethz.rosetta.lastUpdated
2021-02-15T09:43:12Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Streaming%20Complexity%20of%20Spanning%20Tree%20Computation&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2020&rft.volume=154&rft.spage=34&rft.issn=1868-8969&rft.au=Chang,%20Yi-Jun&Farach-Colton,%20Martin&Hsu,%20Tsan-Sheng&Tsai,%20Meng-Tsung&rft.isbn=978-3-95977-140-5&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.STACS.2020.34&rft.btitle=37th%20International%20Symposium%20on%20Theoretical%20Aspects%20of%20Computer%20Science%20(STACS%202020)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record