Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model

Yu-Sheng Shih, Meng-Tsung Tsai, Yen-Chu Tsai +1

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 patte…