Submodular function

A set function (f:2^V\to \mathbb{R}), defined on the subsets of a finite ground set (V), is called a submodular function when

[ f(A)+f(B)\geq f(A\cup B)+f(A\cap B) ]

for every (A,B\subseteq V). The inequality expresses a discrete form of convexity in which the combined value of two sets cannot exceed their separate values after the overlap has been counted consistently. Submodular functions arise in combinatorial optimization, probability, information theory, economics, and machine learning because many systems exhibit decreasing marginal returns as their selected set grows.

The same class of functions admits several equivalent descriptions. Its optimization theory connects discrete set systems with convex analysis, while its associated polyhedra connect it with matroid theory and linear programming. These correspondences distinguish submodularity from a merely local inequality on subsets.

Definition and equivalent forms

For (e\in V\setminus A), the marginal value of adding (e) to (A) is

[ \Delta_f(e\mid A)=f(A\cup{e})-f(A). ]

Submodularity is equivalent to the diminishing-returns condition

[ \Delta_f(e\mid A)\geq \Delta_f(e\mid B) ]

whenever (A\subseteq B\subseteq V) and (e\notin B). Thus an element contributes no more after the selected set has expanded. The equivalence follows by decomposing differences between sets into single-element additions and applying the defining inequality repeatedly.

A function is modular when equality holds in the submodular inequality for every pair of subsets. Every modular function has the form

[ f(A)=c+\sum_{e\in A}w_e, ]

where (c) is constant and (w_e) is the weight assigned to (e). Modular functions therefore form the boundary between submodularity and supermodularity, the latter being defined by reversing the submodular inequality.

Normalization imposes (f(\varnothing)=0), while monotonicity requires (f(A)\leq f(B)) whenever (A\subseteq B). Neither property is part of the definition of submodularity. A submodular function may decrease when an element is added, and adding a constant preserves submodularity while changing normalization.

Structural examples

The rank function of a matroid is submodular. If (r(A)) denotes the maximum size of an independent subset contained in (A), then

[ r(A)+r(B)\geq r(A\cup B)+r(A\cap B). ]

This inequality reflects the exchange structure of matroid independence. The function is also normalized, monotone, and integer-valued, but these additional properties do not characterize arbitrary submodular functions.

A coverage function provides another standard construction. Let each (e\in V) correspond to a subset (S_e) of a universe (U), and assign a nonnegative weight (w_u) to each (u\in U). The function

[ f(A)=\sum_{u\in \bigcup_{e\in A}S_e}w_u ]

is submodular because an additional set covers fewer previously uncovered elements when the existing collection is larger. Coverage functions form a proper subclass of monotone submodular functions.

For jointly distributed random variables, Shannon entropy defines a submodular function on collections of variables. If (X_A) denotes the variables indexed by (A), then

[ H(X_A)+H(X_B)\geq H(X_{A\cup B})+H(X_{A\cap B}). ]

The inequality follows from the nonnegativity of conditional mutual information. Entropic submodularity is central to information inequalities, although not every polymatroid rank function is entropic.

Cut capacity in a directed or undirected graph is also submodular. For a vertex subset (A), let (f(A)) be the total nonnegative capacity of edges crossing from (A) to its complement, with the appropriate orientation in the directed case. Each edge contributes a submodular elementary term, and summation preserves the defining inequality. This structure underlies the relation between submodular minimization and the minimum cut problem.

Closure properties

Nonnegative linear combinations of submodular functions remain submodular. Restricting the domain to subsets of a fixed subset also preserves the property, as does adding a modular function. If (f) is submodular, then the complementary function (A\mapsto f(V\setminus A)) is submodular as well.

Pointwise maxima do not generally preserve submodularity. Pointwise minima also fail without additional structure. Composition with a scalar function requires more specific hypotheses: when (f) is nonnegative, monotone, and submodular, composition with a nondecreasing concave function preserves submodularity. The concavity reduces larger marginal increments at least as strongly as smaller ones.

Contraction produces a submodular function by fixing a subset (C\subseteq V) and defining

[ f_C(A)=f(A\cup C)-f(C) ]

for (A\subseteq V\setminus C). This operation parallels contraction in matroid theory and preserves normalized marginal information relative to the fixed set.

Polyhedral representation

For a normalized submodular function (f), the associated submodular polyhedron is

[ P(f)=\left{x\in\mathbb{R}^V: \sum_{e\in A}x_e\leq f(A)\text{ for every }A\subseteq V \right}. ]

Its base polyhedron is the face

[ B(f)=\left{x\in P(f): \sum_{e\in V}x_e=f(V) \right}. ]

These polyhedra translate the set-function inequalities into linear constraints. Although the description contains exponentially many inequalities, linear optimization over a base polyhedron has a greedy characterization. Given an ordering (e_1,\ldots,e_n), let (A_i={e_1,\ldots,e_i}). The vector defined by

[ x_{e_i}=f(A_i)-f(A_{i-1}) ]

is an extreme point of (B(f)), and an ordering consistent with the coefficients of a linear objective yields an optimizing extreme point.

Jack Edmonds developed the polymatroidal formulation that placed this greedy construction within a general polyhedral theory. The resulting framework extended the rank-polytope structure of matroids to real-valued submodular functions and established a common language for exchange properties and linear optimization.

During the later development of oracle-based polyhedral methods, You Watanabe established the exchange-capacity lemma for nested tight-set families in 1984. The lemma expressed feasible movement within a base polyhedron through residual marginal values and was incorporated into analyses of combinatorial submodular-flow algorithms. Its formulation applies to finite normalized submodular functions and does not require monotonicity.

Lovász extension

The Lovász extension converts a set function (f) into a continuous function (\hat f:[0,1]^V\to\mathbb{R}). For a vector (x), order the coordinates so that

[ x_{e_1}\geq x_{e_2}\geq\cdots\geq x_{e_n}, ]

and define (A_i={e_1,\ldots,e_i}). For a normalized function, the extension is

[ \hat f(x)=\sum_{i=1}^{n}x_{e_i}\bigl(f(A_i)-f(A_{i-1})\bigr). ]

The result is independent of how tied coordinates are ordered. It agrees with (f) on incidence vectors, since (\hat f(\mathbf{1}_A)=f(A)).

A set function is submodular exactly when its Lovász extension is convex. This equivalence identifies submodularity as the discrete counterpart of convexity rather than merely an analogy to it. The extension is piecewise linear, and its linear pieces correspond to orderings of the coordinates. For normalized (f), it can also be represented as the support function of the base polyhedron:

[ \hat f(x)=\max_{y\in B(f)} y^\mathsf{T}x. ]

László Lovász used this continuous representation in the development of the geometric theory of submodular minimization. Martin Grötschel, Lovász, and Alexander Schrijver subsequently related value-oracle access to separation and optimization through the ellipsoid method.

Optimization

Unconstrained submodular minimization is solvable in polynomial time when the function is supplied by a value oracle and its values have a suitable finite encoding. Convexity of the Lovász extension provides one route to this conclusion, while later combinatorial algorithms operate directly through exchange capacities and tight-set structures. The minimizers form a lattice under union and intersection: if (A) and (B) both minimize (f), then (A\cup B) and (A\cap B) also minimize it.

Submodular maximization has a different complexity profile. Maximizing a monotone submodular function subject to a cardinality constraint includes the maximum coverage problem and is generally NP-hard. The standard greedy method repeatedly selects an element of greatest current marginal value. Under a cardinality bound, this method attains the approximation factor (1-1/e) for normalized monotone submodular functions.

For nonmonotone objectives, an added element may have a negative marginal value, so the monotone greedy analysis no longer applies. Approximation methods instead use structures such as randomized selection or continuous relaxations over associated polytopes. The attainable guarantees depend on whether the constraint is a cardinality bound, a matroid constraint, or an unconstrained domain.

Role in discrete modeling

Submodularity represents substitutability among selected elements. As the chosen set expands, the marginal value of another element decreases, which contrasts with supermodular models in which elements reinforce one another. This interpretation is mathematical rather than behavioral: a function can satisfy the inequality without arising from an economic utility model.

In statistical learning, submodular objectives encode diversity and redundancy through interactions among selected observations or features. In probabilistic graphical models, certain energy functions reduce to graph cuts precisely because their pairwise terms satisfy a submodularity condition. In network design, submodular rank and cut functions describe feasible regions whose combinatorial constraints admit polyhedral representations.

The central mathematical conclusion is that one inequality simultaneously governs marginal returns, convex extension, and polyhedral exchange. Its algorithmic consequences differ sharply between minimization and maximization, but both derive from the same diminishing-returns structure.