3SUM Hardness of Triangle Enumeration Problems, and their Consequences
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Proves a chain of reductions from 3SUM hardness to offline set intersection to triangle enumeration to vertex-triangle queries to induced subgraph and finally to online dictionary matching with one gap, yielding a conditional lower bound: triangle enumeration needs Omega(M^{1.5}) total (equivalently Omega(sqrt(M)) per edge/query) under 3SUM, assuming linear preprocessing. Builds an algorithm that orients the graph and runs in O(alpha(G) + output) per query (where alpha is arboricity), and shows this arboricity-dependent algorithm is essentially optimal for any polynomial sparsity regime.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:32Virus Detection
- 2:34Online Dictionary Matching with One Gap
- 3:40Story Time
- 8:18Example
- 8:46Induced Subgraph = ODMOG
- 10:06Algorithm: 0(m + output)
- 12:31Set Intersection CLB from 3SUM
- 13:54Graph Presentation
- 17:33Triangle Enumeration Data Structures
- 17:49Edge-Triangles Queries
- 18:25Vertex-Triangles Queries
- 19:52Vertex-Triangles LB
- 21:08Recap
- 21:46Vertex-Triangles DS = Induced Subgraph
- 23:14Vertex-Triangles Average Degree
- 24:22Upper bound • Orientations
- 26:20Arboricity and Orientations
- 28:11Induced Subgraph summary
- 29:43Triangle Enumeration - optimal algorithm(s)
- 30:44Conclusions
- 31:48Open Question