Department of Mathematics Calendar

Back to Listing

The Department of Mathematics Calendar has moved to Webtools. Anyone may submit an event by clicking the "+" button (upper right). Note: the Sponsor field is required. Just type "n/a"

All events will be reviewed before acceptance. Please email Shelby Koehne if you have any questions about submitting an event.

Note: you may search past and future events by clicking on the magnifying glass icon on the main Calendar page.

For an archive of past events:

Graph Theory and Combinatorics Seminar: Enumerating Min Cut-sets and k-cut-sets in Hypergraphs

Event Type
345 AH
Mar 8, 2022   1:00 pm  
Weihang Wang (UIUC)
Sean English
senglish at illinois dot edu

Given a hypergraph H=(V,E), we consider two problems--Hypergraph Min-cut, where the goal is to find a 2-partition of V that minimizes the number of hyperedges crossing the 2-partition, and Hypergraph k-cut, where the goal is to find a k-partition of V that minimizes the number of hyperedges crossing the k-partition. Our goal is to enumerate all optimum solutions in polynomial time. For each problem, the number of optimum solutions could be exponential, but the number of hyperedge sets corresponding to optimum solutions (denoted min-cut-sets and min-k-cut-sets, respectively) is polynomial (k is a fixed constant for Hypergraph k-cut). Our algorithms enumerate min-cut-sets and min-k-cut-sets (instead of 2-partitions and k-partitions, respectively), relying on structural results that relate optimum min-cut-sets and min-k-cut-sets to min (S,T)-cut for small vertex sets S and T.

This is joint work with Calvin Beideman and Karthekeyan Chandrasekaran.

link for robots only