2026-08-14T21:14:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20166 2024-07-02T07:52:49Z ddc:004 open_access

Splitting-Off in Hypergraphs Bérczi, Kristóf Chandrasekaran, Karthekeyan Király, Tamás Kulkarni, Shubhang Hypergraphs Hypergraph Connectivity Splitting-off Constructive Characterizations Hypergraph Orientations Submodular Functions Combinatorial Optimization 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 [Lov{á}sz, 1974; Lov{á}sz, 1993] and Mader [Mader, 1978] 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 [Lovász, 1976; Mader, 1978; Frank, 1993; Frank and Király, 2002; Király and Lau, 2008; Frank, 1992; Goemans and Bertsimas, 1993; Frank, 1994; Bang-Jensen et al., 1995; Frank, 2011; Nagamochi and Ibaraki, 2008; Nagamochi et al., 1997; Henzinger and Williamson, 1996; Goemans, 2001; Jordán, 2003; Kriesell, 2003; Jain et al., 2003; Chan et al., 2011; Bhalgat et al., 2008; Lau, 2007; Chekuri and Shepherd, 2008; Nägele and Zenklusen, 2020; Blauth and Nägele, 2023]. 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 [Király and Lau, 2008]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristóf Bérczi and Karthekeyan Chandrasekaran and Tamás Király and Shubhang Kulkarni 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.23 urn:nbn:de:0030-drops-201660 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode