License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.24
URN: urn:nbn:de:0030-drops-173808
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17380/
Oostveen, Jelle J. ;
van Leeuwen, Erik Jan
Parameterized Complexity of Streaming Diameter and Connectivity Problems
Abstract
We initiate the investigation of the parameterized complexity of Diameter and Connectivity in the streaming paradigm. On the positive end, we show that knowing a vertex cover of size k allows for algorithms in the Adjacency List (AL) streaming model whose number of passes is constant and memory is ?(log n) for any fixed k. Underlying these algorithms is a method to execute a breadth-first search in ?(k) passes and ?(k log n) bits of memory. On the negative end, we show that many other parameters lead to lower bounds in the AL model, where Ω(n/p) bits of memory is needed for any p-pass algorithm even for constant parameter values. In particular, this holds for graphs with a known modulator (deletion set) of constant size to a graph that has no induced subgraph isomorphic to a fixed graph H, for most H. For some cases, we can also show one-pass, Ω(n log n) bits of memory lower bounds. We also prove a much stronger Ω(n²/p) lower bound for Diameter on bipartite graphs.
Finally, using the insights we developed into streaming parameterized graph exploration algorithms, we show a new streaming kernelization algorithm for computing a vertex cover of size k. This yields a kernel of 2k vertices (with ?(k²) edges) produced as a stream in poly(k) passes and only ?(k log n) bits of memory.
BibTeX - Entry
@InProceedings{oostveen_et_al:LIPIcs.IPEC.2022.24,
author = {Oostveen, Jelle J. and van Leeuwen, Erik Jan},
title = {{Parameterized Complexity of Streaming Diameter and Connectivity Problems}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {24:1--24:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17380},
URN = {urn:nbn:de:0030-drops-173808},
doi = {10.4230/LIPIcs.IPEC.2022.24},
annote = {Keywords: Stream, Streaming, Graphs, Parameter, Complexity, Diameter, Connectivity, Vertex Cover, Disjointness, Permutation}
}
|
Keywords: |
|
Stream, Streaming, Graphs, Parameter, Complexity, Diameter, Connectivity, Vertex Cover, Disjointness, Permutation |
|
Collection: |
|
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
