Splitting-Off in Hypergraphs

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Shubhang Kulkarni

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

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 [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.

Original languageEnglish (US)
Title of host publication51st International Colloquium on Automata, Languages, and Programming, ICALP 2024
EditorsKarl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773225
DOIs
StatePublished - Jul 2024
Event51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 - Tallinn, Estonia
Duration: Jul 8 2024Jul 12 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume297
ISSN (Print)1868-8969

Conference

Conference51st International Colloquium on Automata, Languages, and Programming, ICALP 2024
Country/TerritoryEstonia
CityTallinn
Period7/8/247/12/24

Keywords

  • Combinatorial Optimization
  • Constructive Characterizations
  • Hypergraph Connectivity
  • Hypergraph Orientations
  • Hypergraphs
  • Splitting-off
  • Submodular Functions

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Splitting-Off in Hypergraphs'. Together they form a unique fingerprint.

Cite this