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 -