Speaker: Shubhang Kulkarni (UIUC)
Title: Splitting-off in Hypergraphs
Abstract: The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász (1974) and Mader (1978) showed the existence of this operation while preserving global and local connectivities respectively in graphs under mild conditions. In this talk, I will introduce a notion of splitting-off in hypergraphs. I will use this notion to show two applications: (i) the edge-capacitated version of Menger’s theorem in graphs and (ii) an approximate min-max relation for the max Steiner rooted-connected orientation problem.
Based on joint work with Kristóf Bérczi (Eötvös Loránd University), Karthekeyan Chandrasekaran (UIUC), and Tamás Király (Eötvös Loránd University).
