2022/12/01 by Huang, Zhiyi, Long, Yaowei, Saranurak, Thatchaphol +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2212.00359
We study the fine-grained complexity of graph connectivity problems in unweighted undirected graphs. Recent development shows that all variants of edge connectivity problems, including single-source-single-sink, global, Steiner, single-source, and all-pairs connectivity, are solvable in m1+o(1) time, collapsing the complexity of these problems into the almost-linear-time regime. While, historically, vertex connectivity has been much harder, the recent results showed that both single-source-single-sink and global vertex connectivity can be solved in m1+o(1) time, raising the hope of putting all variants of vertex connectivity problems into the almost-linear-time regime too. We show that this hope is impossible, assuming conjectures on finding 4-cliques. Moreover, we essentially settle the complexity landscape by giving tight bounds for combinatorial algorithms in dense graphs. There are three separate regimes: (1) all-pairs and Steiner vertex connectivity have complexity Θ(n4), (2) single-source vertex connectivity has complexity Θ(n3), and (3) single-source-single-sink and global vertex connectivity have complexity Θ(n2). For graphs with general density, we obtain tight bounds of Θ(m2), Θ(m1.5), Θ(m), respectively, assuming Gomory-Hu trees for element connectivity can be computed in almost-linear time.