TY - GEN

T1 - Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition

AU - Beideman, Calvin

AU - Chandrasekaran, Karthekeyan

AU - Mukhopadhyay, Sagnik

AU - Nanongkai, Danupon

N1 - Funding Information:
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672. The last two authors are also supported by the Swedish Research Council (Reg. No. 2015-04659 and 2019-05622). Karthekeyan and Calvin are supported in part by NSF grants CCF-1814613 and CCF-1907937.
Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - The connectivity of a hypergraph is the minimum number of hyperedges whose deletion disconnects the hypergraph. We design an O^r(p+min{λr-3r-1n2,nr/λrr-1,λ5r-74r-4n74}) (The O^r(· ) notation hides terms that are subpolynomial in the main parameter and terms that depend only on r) time algorithm for computing hypergraph connectivity, where p: = ∑e ∈ E| e| is the input size of the hypergraph, n is the number of vertices, r is the rank (size of the largest hyperedge), and λ is the connectivity of the input hypergraph. Our algorithm also finds a minimum cut in the hypergraph. Our algorithm is faster than existing algorithms if r= O(1 ) and λ= nΩ ( 1 ). The heart of our algorithm is a structural result showing a trade-off between the number of hyperedges taking part in all minimum cuts and the size of the smaller side of any minimum cut. This structural result can be viewed as a generalization of an acclaimed structural theorem for simple graphs [Kawarabayashi-Thorup, JACM 19 (Fulkerson Prize 2021)]. We extend the framework of expander decomposition to hypergraphs to prove this structural result. In addition to the expander decomposition framework, our faster algorithm also relies on a new near-linear time procedure to compute connectivity when one of the sides in a minimum cut is small.

AB - The connectivity of a hypergraph is the minimum number of hyperedges whose deletion disconnects the hypergraph. We design an O^r(p+min{λr-3r-1n2,nr/λrr-1,λ5r-74r-4n74}) (The O^r(· ) notation hides terms that are subpolynomial in the main parameter and terms that depend only on r) time algorithm for computing hypergraph connectivity, where p: = ∑e ∈ E| e| is the input size of the hypergraph, n is the number of vertices, r is the rank (size of the largest hyperedge), and λ is the connectivity of the input hypergraph. Our algorithm also finds a minimum cut in the hypergraph. Our algorithm is faster than existing algorithms if r= O(1 ) and λ= nΩ ( 1 ). The heart of our algorithm is a structural result showing a trade-off between the number of hyperedges taking part in all minimum cuts and the size of the smaller side of any minimum cut. This structural result can be viewed as a generalization of an acclaimed structural theorem for simple graphs [Kawarabayashi-Thorup, JACM 19 (Fulkerson Prize 2021)]. We extend the framework of expander decomposition to hypergraphs to prove this structural result. In addition to the expander decomposition framework, our faster algorithm also relies on a new near-linear time procedure to compute connectivity when one of the sides in a minimum cut is small.

KW - Connectivity

KW - Expander decomposition

KW - Hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=85131919833&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131919833&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-06901-7_6

DO - 10.1007/978-3-031-06901-7_6

M3 - Conference contribution

AN - SCOPUS:85131919833

SN - 9783031069000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 70

EP - 83

BT - Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings

A2 - Aardal, Karen

A2 - Sanità, Laura

PB - Springer

T2 - 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022

Y2 - 27 June 2022 through 29 June 2022

ER -