Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.10710
curl -X POST /api/v1/records/arxiv/2603.10710/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.10710/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'