2026-07-21T23:49:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23426 2025-10-02T12:54:48Z ddc:004 open_access

Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game Chen, Antares Orecchia, Lorenzo Tani, Erasmo Hypergraph Partitioning Cut Improvement Cut-Matching Game Despite there being significant work on developing spectral- [Chan et al., 2018; Lau et al., 2023; Kwok et al., 2022], and metric-embedding-based [Louis and Makarychev, 2016] approximation algorithms for hypergraph conductance, little is known regarding the approximability of other hypergraph partitioning objectives. This work proposes algorithms for a general model of hypergraph partitioning that unifies both undirected and directed versions of many well-studied partitioning objectives. The first contribution of this paper introduces polymatroidal cut functions, a large class of cut functions amenable to approximation algorithms via metric embeddings and routing multicommodity flows. We demonstrate a simple O(√{log n})-approximation, where n is the number of vertices in the hypergraph, for these problems by rounding relaxations to metrics of negative-type. The second contribution of this paper generalizes the cut-matching game framework of Khandekar et al. [Khandekar et al., 2007] to tackle polymatroidal cut functions. This yields an almost-linear time O(log n)-approximation algorithm for standard versions of undirected and directed hypergraph partitioning [Kwok et al., 2022]. A technical contribution of our construction is a novel cut-matching game, which greatly relaxes the set of allowed actions by the cut player and allows for the use of approximate s-t maximum flows by the matching player. We believe this to be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antares Chen and Lorenzo Orecchia and Erasmo Tani 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.49 urn:nbn:de:0030-drops-234261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.49 eng https://creativecommons.org/licenses/by/4.0/legalcode