A Unified Approach to Minimizing Symmetric Submodular Functions

Satoru Iwata, Haruto Konno · 2026

Read A Unified Approach to Minimizing Symmetric Submodular Functions by Satoru Iwata, Haruto Konno (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-01473.txt.

Introduction

Satoru Iwata and Haruto Konno unify two classic algorithms for shrinking symmetric submodular functions, a family of set functions with a diminishing-returns shape that shows up in cuts, clustering, and entropy. Two orderings of the ground set, built decades apart, each expose a special pair of elements that lets the search contract and continue.

One ordering yields a pendent pair and the other a flat pair, and the link between them was never clear. Iwata and Konno add a third ordering, then stretch all three into a one-parameter family. A single general inequality governs the family, and the two classic results drop out at the two ends of the dial. At every setting, the last two elements of the ordering form a contractible pair, which gives one contraction algorithm that finds a nontrivial minimizer with a cubic number of value queries.

Catalog record

CREATORSatoru Iwata, Haruto Konno
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.01473

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Unified Approach to Minimizing Symmetric Submodular Functions Satoru Iwata, Haruto Konno Abstract Symmetric submodular function minimization admits purely combinatorial algorithms using special orderings of the ground set. Extending the minimum-cut algorithm of Nagamochi and Ibaraki (1992), Queyranne (1998) showed that the maximum adjacency ordering yields a pendent pair, which can be used to find a nontrivial minimizer. Nagamochi (2010) later introduced the minimum degree ordering, which yields a flat pair and leads to the identification of extreme sets. Despite the apparent similarity between these two algorithms, their connection remained unclear. In this paper, we introduce yet another ordering called minimum capacity ordering, and extend it to a one-parameter family of orderings, called α \alpha -orderings, that unifies these two previously known orderings. We prove a general inequality for α \alpha -orderings, and our framework recovers the known pendent-pair and flat-pair results as special cases, corresponding to α = − 1 \alpha=-1 and α = 1 \alpha=1 , respectively. For each α ∈ [ − 1 , 1 ] \alpha\in[-1,1] , the last two elements of an α \alpha -ordering form a contractible pair, i.e., a pair whose contraction preserves the existence of a nontrivial minimizer, which leads to a contraction algorithm that finds a nontrivial minimizer of a symmetric submodular function in O ⁡ ( n 3 ) O(n^{3}) oracle calls, where n n is the cardinality of the ground set. In addition, we discuss the ranges of α \alpha that ensure α \alpha -ordering to obtain these special pairs. 1 Introduction Let V be a finite set of cardinality n . We denote by \mathbb{R} and \mathbb{R}_{+} the sets of reals and nonnegative reals, respectively. A set function f:2^{V}\to\mathbb{R} is called submodular if f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y),\qquad\forall X,Y\subseteq V. Submodularity is a fundamental notion in discrete optimization. It has been studied through central structures such as matroids, polyhedra, and convexity [ 2 , 6 , 15 ] . The general problem of minimizing a submodular function has a long history. The first polynomial-time algorithm was obtained via the ellipsoid method by Grötschel, Lovász, and Schrijver [ 8 ] , and combinatorial strongly polynomial algorithms were developed later by Iwata, Fleischer, and Fujishige [ 9 ] and by Schrijver [ 22 ] , followed by subsequent improvements [ 1 , 11 , 10 , 14 , 19 ] . The current best bound on oracle calls in a strongly polynomial algorithm is O(n^{3}\log\log n/\log n) due to Jiang [ 12 ] . In this paper, we focus on the symmetric case. A set function f:2^{V}\to\mathbb{R} is called symmetric if f(X)=f(V\setminus X),\qquad\forall X\subseteq V. Symmetric submodular functions form an important subclass of submodular functions. Fujishige [ 4 ] studied their structural properties and established a decomposition theory for them. For a symmetric submodular function f , both \varnothing and V are always minimizers. Accordingly, the symmetric submodular function minimization problem asks for a nontrivial minimizer, i.e., a proper nonempty subset that achieves the minimum value. A canonical example of a symmetric submodular function is the cut capacity function of a capacitated undirected graph. For an undirected graph G=(V,E) with an edge capacity function c:E\to\mathbb{R}_{+} , its cut capacity function \kappa:2^{V}\to\mathbb{R}_{+} is defined by \kappa(X):=\sum_{\{u,v\}\in E:\,|\{u,v\}\cap X|=1}c(u,v)\qquad(\forall X\subseteq V), which is symmetric and submodular. The minimization of the cut function over nonempty proper subsets coincides with the global minimum-cut problem in an undirected graph. A straightforward polynomial-time approach to this problem is to fix a vertex s\in V , compute a minimum (s,t) -cut for each t\in V\setminus\{s\} by a max-flow algorithm, and take the best one. A key combinatorial approach to this problem originates in Nagamochi and Ibaraki [ 17 ] , whose correctness proof was later simplified by Frank [ 3 ] and by Stoer and Wagner [ 23 ] . The method is based on constructing a maximum adjacency ordering (MA-ordering) of the vertices and using the fact that the last two vertices in such an ordering form a pendent pair . This implies that, among all cuts separating these two vertices, a minimum one is already represented by a singleton side, so the pair can be contracted without losing any information needed to recover a global minimum cut. Repeating this contraction step leads to one of the simplest and fastest deterministic global minimum-cut algorithms. Queyranne [ 20 ] extended this ordering-based contraction framework from graph cut functions to arbitrary symmetric submodular functions, thereby obtaining a combinatorial strongly polynomial algorithm that finds a nontrivial minimizer in O(n^{3}) oracle calls. For symmetric submodular function minimization, this approach remains substantially simpler and faster than using strongly polynomial algorithms for general submodular function minimization O(n) times. More recently, Nagamochi [ 18 ] introduced the minimum degree ordering (MD-ordering) and proved that the last two vertices in such an ordering form a flat pair . In the graph setting, contracting flat pairs yields not only a minimum cut but also all extreme sets (extreme subsets, or LS-sets), which capture a finer structure of the connectivity function. The notion of extreme sets predates this ordering-based framework: it was introduced by Luccio and Sami [ 16 ] as a compact representation of graph connectivity through decomposition into minimally interconnected subnetworks, and was later applied by Lawler [ 13 ] to hypergraph partitioning. Nagamochi [ 18 ] further extended this viewpoint to symmetric submodular functions, showing that the ordering-based contraction framework can recover not only a nontrivial minimizer but also the finer structural information encoded by extreme sets with O(n^{3}) oracle calls. Exploiting the property of pendent pairs obtained by MA-ordering, Goemans and Soto [ 7 ] presented an algorithm that finds a nontrivial minimizer of a symmetric submodular function in a hereditary family of subsets using O(n^{3}) oracle calls. They further extended this algorithm to enumerate all minimal such optimal sets in the same asymptotic running time. Unlike symmetric submodular function minimization, the problem itself breaks symmetry, and the MD-ordering has not been applied to solve the same problem. In contrast, Goemans and Soto [ 7 ] also described an algorithm that enumerates all extreme sets of a symmetric submodular function using O(n^{4}) oracle calls, whereas Nagamochi’s algorithm achieves the same goal more efficiently. Thus, MA- and MD-orderings have their own advantages. From a higher perspective, however, the similarity between the algorithms of Queyranne and Nagamochi suggests that the MA- and MD-orderings should be viewed not as isolated constructions, but as manifestations of a broader common principle. The purpose of this paper is to clarify their common structure. To capture the algorithmic content of the pairs of elements obtained at the end of these orderings, we introduce the notion of a contractible pair . This is a weaker property than being a pendent pair or a flat pair, but it is still sufficient to support a contraction algorithm for finding a nontrivial minimizer. We also introduce yet another ordering called the minimum capacity ordering (MC-ordering). Our first main result (Theorem 4 ) shows that the last two elements of an MC-ordering form a contractible pair, thereby obtaining the third ordering-based combinatorial algorithm for finding a nontrivial minimizer of a symmetric submodular function with O(n^{3}) oracle calls. We then extend the MC-ordering to a one-parameter

Read the complete text