TY - GEN
T1 - Splitting-Off in Hypergraphs
AU - Bérczi, Kristóf
AU - Chandrasekaran, Karthekeyan
AU - Király, Tamás
AU - Kulkarni, Shubhang
N1 - Publisher Copyright:
© Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni.
PY - 2024/7
Y1 - 2024/7
N2 - 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 [45,47] and Mader [48] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [2,7,8,12,17,22,23,24,25,26, 29,30,32,33,35,38,40,41,46,48,49,50,51]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [38]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams’ strong orientation theorem and uses tools developed for hypergraphs.
AB - 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 [45,47] and Mader [48] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [2,7,8,12,17,22,23,24,25,26, 29,30,32,33,35,38,40,41,46,48,49,50,51]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [38]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams’ strong orientation theorem and uses tools developed for hypergraphs.
KW - Combinatorial Optimization
KW - Constructive Characterizations
KW - Hypergraph Connectivity
KW - Hypergraph Orientations
KW - Hypergraphs
KW - Splitting-off
KW - Submodular Functions
UR - http://www.scopus.com/inward/record.url?scp=85198344169&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85198344169&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2024.23
DO - 10.4230/LIPIcs.ICALP.2024.23
M3 - Conference contribution
AN - SCOPUS:85198344169
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024
A2 - Bringmann, Karl
A2 - Grohe, Martin
A2 - Puppis, Gabriele
A2 - Svensson, Ola
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024
Y2 - 8 July 2024 through 12 July 2024
ER -