Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition

Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings
EditorsKaren Aardal, Laura Sanità
Number of pages14
ISBN (Print)9783031069000
StatePublished - 2022
Event23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands
Duration: Jun 27 2022Jun 29 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13265 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022


  • Connectivity
  • Expander decomposition
  • Hypergraphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition'. Together they form a unique fingerprint.

Cite this