Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 24 min ago
PreprintCC BY 4.0arXiv

All minimum cuts of symmetric submodular functions

  • Chao Xu
Open at sourcePDFDOICite

Abstract

We compute Cunningham's canonical decomposition of a symmetric submodular function on n elements in O(n3) time. The decomposition represents all minimum cuts in linear space. For the pair s,t produced by Queyranne's algorithm, we construct in O(n2) 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.

Related

  1. Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
    Zhongqi Wu, Taotao He, Mohit Tawarmalani
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Counterexamples to the Minimum Period Conjecture for Restricted Partition Functions
    Feihu Liu, Jinlong Tang, Guoce Xin +1
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
    Rostislav Klech
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  4. Closed formula for Kronecker structure constants of a molecular basis of homogeneous symmetric functions
    Josaphat W. V. Baolahy, Benjamin Randrianirina
    Enumerative Combinatorics and ApplicationsPeer-reviewedCC BY-NDFull textCombinatorics & discrete mathematicsDOAJ
  5. A zero-density estimate for the symmetric square L-functions in the weight aspect
    Songchen Yin
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026minimum,
  title = {{All minimum cuts of symmetric submodular functions}},
  author = {Chao Xu},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.08253},
  eprint = {2611.08253},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08253},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - All minimum cuts of symmetric submodular functions
AU  - Chao Xu
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.08253
UR  - https://arxiv.org/abs/2611.08253
AB  - 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.
ER  -