# On the Complexity of Submodular Function Minimisation on Diamonds

Research paper by **Fredrik Kuivinen**

Indexed on: **21 Apr '09**Published on: **21 Apr '09**Published in: **Computer Science - Data Structures and Algorithms**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $(L; \sqcap, \sqcup)$ be a finite lattice and let $n$ be a positive
integer. A function $f : L^n \to \mathbb{R}$ is said to be submodular if
$f(\tup{a} \sqcap \tup{b}) + f(\tup{a} \sqcup \tup{b}) \leq f(\tup{a}) +
f(\tup{b})$ for all $\tup{a}, \tup{b} \in L^n$. In this paper we study
submodular functions when $L$ is a diamond. Given oracle access to $f$ we are
interested in finding $\tup{x} \in L^n$ such that $f(\tup{x}) = \min_{\tup{y}
\in L^n} f(\tup{y})$ as efficiently as possible.
We establish a min--max theorem, which states that the minimum of the
submodular function is equal to the maximum of a certain function defined over
a certain polyhedron; and a good characterisation of the minimisation problem,
i.e., we show that given an oracle for computing a submodular $f : L^n \to
\mathbb{Z}$ and an integer $m$ such that $\min_{\tup{x} \in L^n} f(\tup{x}) =
m$, there is a proof of this fact which can be verified in time polynomial in
$n$ and $\max_{\tup{t} \in L^n} \log |f(\tup{t})|$; and a pseudo-polynomial
time algorithm for the minimisation problem, i.e., given an oracle for
computing a submodular $f : L^n \to \mathbb{Z}$ one can find $\min_{\tup{t} \in
L^n} f(\tup{t})$ in time bounded by a polynomial in $n$ and $\max_{\tup{t} \in
L^n} |f(\tup{t})|$.