Id: arxiv/2611.08253 Url: https://arxiv.org/abs/2611.08253 Tags: cs.DS, math.CO, math.OC Score: 0 Title: All minimum cuts of symmetric submodular functions Domain: cs.DS Source: arxiv Authors: Chao Xu Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.08253 We compute Cunningham's canonical decomposition of a symmetric submodular function on $n$ elements in $O(n^3)$ time. The decomposition represents all minimum cuts in linear space. For the pair $s,t$ produced by Queyranne's algorithm, we construct in $O(n^2)$ time a digraph representing exactly the minimum $st$-cuts of the function. Using this construction in Chekuri and Xu's decomposition algorithm gives the cubic bound.