2026-08-25T14:43:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27168 2026-08-25T13:18:16Z ddc:004 open_access

Polynomial-Size Encoding of All Cuts of Small Value in Integer-Valued Symmetric Submodular Functions Oum, Sang-il Sokołowski, Marek Connectivity function Symmetric Submodular Function Submodular Minimum Bisection We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining 0 on the empty set. For a connectivity function f on an n-element set V and an integer k ≥ 0, we show that the family of all sets X ⊆ V with f(X) = k admits a polynomial-size representation: it can be described by a list of at most O(n^{4k}) items, each consisting of a set to be included, another set to be excluded, and a partition of remaining elements, such that the union of some members of the partition and the set to be included are precisely all sets X with f(X) = k. We also give an algorithm that constructs this representation in time O(n^{2k+7}γ+n^{2k+8}+n^{4k+2}), where γ is the oracle time to evaluate f. This generalizes the low rank structure theorem of Bojańczyk, Pilipczuk, Przybyszewski, Sokołowski, and Stamoulis [Low rank MSO, LICS 2026] on cut-rank functions on graphs to general connectivity functions. As an application, for fixed k, we obtain a polynomial-time algorithm for finding a set A with f(A) = k and a prescribed cardinality constraint on A. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sang-il Oum and Marek Sokołowski 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.32 urn:nbn:de:0030-drops-271680 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode