Fine-Grained Complexity and Conditional Hardness for Sparse Graphs

Udit Agarwal, Vijaya Ramachandran

We consider the fine-grained complexity of sparse graph problems that currently have $\tilde{O}(mn)$ time algorithms, where m is the number of edges and n is the number of vertices…