{"id":"arxiv/2603.10710","url":"https://arxiv.org/abs/2603.10710","tags":["math.CO","cs.DS"],"score":0,"title":"Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions","domain":"math.CO","source":"arxiv","authors":["Sang-il Oum","Marek Sokołowski"],"reviews":0,"subject":"math.CO","summary":"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\\ge 0$, we show that the family of all sets $X\\subseteq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-11","reactions":{}}