Vertex Connectivity in Poly-Logarithmic Max-Flows

Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

22 Sitaatiot (Scopus)

Abstrakti

The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (mα) time for any α ≥ 1, if there is a mα-time maxflow algorithm. Using the current best maxflow algorithm that runs in m4/3+o(1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m4/3+o(1)-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ(mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (m)-time maxflow algorithm. Our new technique is robust enough to also improve the best Õ(mn)-time bound for directed vertex connectivity to mn1−1/12+o(1) time
AlkuperäiskieliEnglanti
OtsikkoProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
ToimittajatSamir Khuller, Virginia Vassilevska Williams
JulkaisupaikkaNew York, NY, USA
KustantajaACM
Sivut317–329
Sivumäärä13
ISBN (painettu)978-1-4503-8053-9
DOI - pysyväislinkit
TilaJulkaistu - 15 kesäk. 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM Symposium on Theory of Computing - Virtual, Online
Kesto: 21 kesäk. 202125 kesäk. 2021

Julkaisusarja

NimiSTOC 2021
KustantajaAssociation for Computing Machinery

Conference

ConferenceACM Symposium on Theory of Computing
LyhennettäSTOC
KaupunkiVirtual, Online
Ajanjakso21/06/202125/06/2021

Sormenjälki

Sukella tutkimusaiheisiin 'Vertex Connectivity in Poly-Logarithmic Max-Flows'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä