Parameterized Complexity of Streaming Diameter and Connectivity Problems
| Autor: | Oostveen, Jelle J., van Leeuwen, Erik Jan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Connectivity Discrete Mathematics (cs.DM) Disjointness Parameter Permutation Complexity Computational Complexity (cs.CC) Theory of computation → Lower bounds and information complexity Streaming Computer Science - Computational Complexity Diameter Computer Science - Data Structures and Algorithms Theory of computation → Streaming sublinear and near linear time algorithms Vertex Cover Stream Theory of computation → Parameterized complexity and exact algorithms Data Structures and Algorithms (cs.DS) Graphs Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.4230/lipics.ipec.2022.24 |
| Popis: | 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 $O(\log n)$ for any fixed $k$. Underlying these algorithms is a method to execute a breadth-first search in $O(k)$ passes and $O(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 $\Omega(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, $\Omega(n \log n)$ bits of memory lower bounds. We also prove a much stronger $\Omega(n^2/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 $O(k^2)$ edges) produced as a stream in $\text{poly}(k)$ passes and only $O(k \log n)$ bits of memory. Comment: 37 pages, 14 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|