# 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 be a finite set, i.e. . A function is called*submodular*if and only if

for all subsets .

### Example 1

Let and with

and .

Then the function f is submodular.

### Definition (supermodular)

A function is called supermodular if and only if the function 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 for all we have

for all subsets ..

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

### Example 3

Let be a directed graph with node set and edge set . Further let

- ,
- and

for all node sets . Let . Then the cut functions

- ,
- and

are submodular.