# Submodular functions

## Contents |

### Introduction

Submodular functions play an important role in combinatorial optimization. A nice property of submodular functions is that minimizing over submodular functions can be done in polynomial time. We will give some examples for submodular functions, such as appropiately defined cut functions in directed (as well as in undirected) graphs. But first we give a formal definition of submodularity.

### Definition (submodular)

Let*E*be a finite set, i.e. |

*E*| < ∞. A function is called

*submodular*if and only if

for all subsets *A*, *B* ⊆ *E*.

### Example 1

Let *E* = {0,1} and with

and .

Then the function f is submodular.

### Definition (supermodular)

A function is called supermodular if and only if the function ( −*f*) is submodular. If a function is both submodular and supermodular, it is called modular.

In formulae, a function is

- supermodular if
- modular if

for all subsets

### Example 2

Let and with andfor all subsets .

This function f is modular. In the special case of *w*_{e} = 1 for all *e* ∈ *E* we have

.f(A) = |A| for all subsets .

That is, the function value for a subset *A* equals the cardinality of *A*.

### Example 3

Let *G* = (*V*,*E*) be a directed graph with node set *V* and edge set *E*. Further let

- ,
- and

for all node sets *S* ⊆ *V*. Let . Then the cut functions

- ,
- and

are submodular.