Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911431942733824 |
|---|---|
| author | Shih, Yu-Sheng Tsai, Meng-Tsung Tsai, Yen-Chu Wu, Ying-Sian |
| author_facet | Shih, Yu-Sheng Tsai, Meng-Tsung Tsai, Yen-Chu Wu, Ying-Sian |
| contents | We study the space complexity of four variants of the standard subgraph finding problem in the streaming model. Specifically, given an $n$-vertex input graph and a fixed-size pattern graph, we consider two settings: undirected simple graphs, denoted by $G$ and $H$, and oriented graphs, denoted by $\vec{G}$ and $\vec{H}$. Depending on the setting, the task is to decide whether $G$ contains $H$ as a subgraph or as an induced subgraph, or whether $\vec{G}$ contains $\vec{H}$ as a subgraph or as an induced subgraph. Let Sub$(H)$, IndSub$(H)$, Sub$(\vec{H})$, and IndSub$(\vec{H})$ denote these four variants, respectively.
An oriented graph is well-oriented if it admits a bipartition in which every arc is oriented from one part to the other, and a vertex is non-well-oriented if both its in-degree and out-degree are non-zero. For each variant, we obtain a complete dichotomy theorem, briefly summarized as follows.
(1) Sub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if $H$ is bipartite.
(2) IndSub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if $H \in \{P_3, P_4, co\mbox{-}P_3\}$.
(3) Sub$(\vec{H})$ can be solved by a single-pass $n^{2-Ω(1)}$-space algorithm if and only if every connected component of $\vec H$ is either a well-oriented bipartite graph or a tree containing at most one non-well-oriented vertex.
(4) IndSub$(\vec{H})$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if the underlying undirected simple graph $H$ is a $co\mbox{-}P_3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08002 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model Shih, Yu-Sheng Tsai, Meng-Tsung Tsai, Yen-Chu Wu, Ying-Sian Data Structures and Algorithms Computational Complexity We study the space complexity of four variants of the standard subgraph finding problem in the streaming model. Specifically, given an $n$-vertex input graph and a fixed-size pattern graph, we consider two settings: undirected simple graphs, denoted by $G$ and $H$, and oriented graphs, denoted by $\vec{G}$ and $\vec{H}$. Depending on the setting, the task is to decide whether $G$ contains $H$ as a subgraph or as an induced subgraph, or whether $\vec{G}$ contains $\vec{H}$ as a subgraph or as an induced subgraph. Let Sub$(H)$, IndSub$(H)$, Sub$(\vec{H})$, and IndSub$(\vec{H})$ denote these four variants, respectively. An oriented graph is well-oriented if it admits a bipartition in which every arc is oriented from one part to the other, and a vertex is non-well-oriented if both its in-degree and out-degree are non-zero. For each variant, we obtain a complete dichotomy theorem, briefly summarized as follows. (1) Sub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if $H$ is bipartite. (2) IndSub$(H)$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if $H \in \{P_3, P_4, co\mbox{-}P_3\}$. (3) Sub$(\vec{H})$ can be solved by a single-pass $n^{2-Ω(1)}$-space algorithm if and only if every connected component of $\vec H$ is either a well-oriented bipartite graph or a tree containing at most one non-well-oriented vertex. (4) IndSub$(\vec{H})$ can be solved by an $\tilde{O}(1)$-pass $n^{2-Ω(1)}$-space algorithm if and only if the underlying undirected simple graph $H$ is a $co\mbox{-}P_3$. |
| title | Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2602.08002 |