Imagen de Portada

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Shih, Yu-Sheng, Tsai, Meng-Tsung, Tsai, Yen-Chu, Wu, Ying-Sian
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Dichotomy Theorem for Multi-Pass Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
por: Dey, Palash, et al.
Publicado: (2026)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
por: Abboud, Amir, et al.
Publicado: (2026)

The Complexity of Finding and Counting Subtournaments
por: Döring, Simon, et al.
Publicado: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
por: Liu, Yang P., et al.
Publicado: (2026)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
por: Oostveen, Jelle J., et al.
Publicado: (2022)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
por: Chou, Chi-Ning, et al.
Publicado: (2021)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
por: Assadi, Sepehr, et al.
Publicado: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
por: Bentert, Matthias, et al.
Publicado: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
por: Laekhanukit, Bundit, et al.
Publicado: (2026)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
por: Curticapean, Radu, et al.
Publicado: (2025)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
por: de Berg, Mark, et al.
Publicado: (2025)

On the Space Complexity of Online Convolution
por: Andersson, Joel Daniel, et al.
Publicado: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
por: Braverman, Mark, et al.
Publicado: (2024)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
por: Curticapean, Radu, et al.
Publicado: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
por: Jiang, Cheng, et al.
Publicado: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
por: Chudigiewitsch, Florian, et al.
Publicado: (2026)

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
por: Döring, Simon, et al.
Publicado: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
por: Nederlof, Jesper
Publicado: (2026)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
por: Grüttemeier, Niels, et al.
Publicado: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
por: Ye, Daniel
Publicado: (2025)

Coloring Graphs with Few Colors in the Streaming Model
por: Assadi, Sepehr, et al.
Publicado: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
por: Focke, Jacob, et al.
Publicado: (2023)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
por: Lehner, Lisa, et al.
Publicado: (2025)

A Dichotomy for Maximum PCSPs on Graphs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2024)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
por: Mu, Ta-Yu, et al.
Publicado: (2024)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
por: Zhang, Bingwei, et al.
Publicado: (2026)

Streaming Zero-Knowledge Proofs
por: Cormode, Graham, et al.
Publicado: (2023)

Efficient Streaming Algorithms for Two-Dimensional Congruence Testing and Geometric Hashing
por: Chang, Yen-Cheng, et al.
Publicado: (2026)

Kernelization Complexity of Solution Discovery Problems
por: Grobler, Mario, et al.
Publicado: (2024)

Streaming approximation resistance of every ordering CSP
por: Singer, Noah G., et al.
Publicado: (2021)

Semi-Streaming Algorithms for Graph Property Certification
por: Das, Avinandan, et al.
Publicado: (2025)

Complexity of Finding and Enumerating Interconnection Trees
por: Demange, Noé, et al.
Publicado: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
por: Sharma, Amatya, et al.
Publicado: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
por: Wang, Yichuan
Publicado: (2024)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
por: Li, Qian, et al.
Publicado: (2025)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
por: Yu, Xifan, et al.
Publicado: (2024)