2026-08-07T18:21:49Z https://drops.dagstuhl.de/oai

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

Cut Sparsification and Succinct Representation of Submodular Hypergraphs Kenneth, Yotam Krauthgamer, Robert Cut Sparsification Submodular Hypergraphs Succinct Representation In cut sparsification, all cuts of a hypergraph H = (V,E,w) are approximated within 1±ε factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge e is provided by a splitting function g_e: 2^e → ℝ_+. This generalization is called a submodular hypergraph when the functions {g_e}_{e ∈ E} are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work studied the setting where H' is a reweighted sub-hypergraph of H, and measured the size of H' by the number of hyperedges in it. In this setting, we present two results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n = |V| and ε^{-1}; (ii) we propose a new parameter, called spread, and use it to obtain smaller sparsifiers in some cases. We also show that for a natural family of splitting functions, relaxing the requirement that H' be a reweighted sub-hypergraph of H yields a substantially smaller encoding of the cuts of H (almost a factor n in the number of bits). This is in contrast to graphs, where the most succinct representation is attained by reweighted subgraphs. A new tool in our construction of succinct representation is the notion of deformation, where a splitting function g_e is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yotam Kenneth and Robert Krauthgamer 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.97 urn:nbn:de:0030-drops-202406 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.97 eng https://creativecommons.org/licenses/by/4.0/legalcode