# Deterministic Small Vertex Connectivity in Almost Linear Time

Preprint · Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

- Archive id: arxiv:2210.13739
- Published: 2022-10-25
- arXiv: https://arxiv.org/abs/2210.13739
- Source URL: https://arxiv.org/abs/2210.13739
- PDF: https://arxiv.org/pdf/2210.13739
- Provenance: arxiv

## Abstract

In the vertex connectivity problem, given an undirected $n$-vertex $m$-edge graph $G$, we need to compute the minimum number of vertices that can disconnect $G$ after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work \[Nanongkai et al.~STOC'19;SODA'20;STOC'21\] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced maxflow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm \[Gabow FOCS'00\] takes $O(m(n+\\min\\{c^{5/2},cn^{3/4}\\}))$ time where $c$ is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant $c\>3$. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants $c$. Our running time is $m^{1+o(1)}2^{O(c^{2})}$ time, which is almost-linear for all $c=o(\\sqrt{\\log n})$. This is the first deterministic algorithm that breaks the $O(n^{2})$-time bound on sparse graphs where $m=O(n)$, which is known for more than 50 years ago \[Kleitman'69\]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström \[FOCS'12\] requires large polynomial time and is randomized.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.