  Techniques based on minimal graph cuts have become a standard tool for
solving combinatorial optimization problems arising in image processing and
computer vision applications. These techniques can be used to minimize
objective functions written as the sum of a set of unary and pairwise terms,
provided that the objective function is submodular. This can be interpreted as
minimizing the $l_1$-norm of the vector containing all pairwise and unary
terms. By raising each term to a power $p$, the same technique can also be used
to minimize the $l_p$-norm of the vector. Unfortunately, the submodularity of
an $l_1$-norm objective function does not guarantee the submodularity of the
corresponding $l_p$-norm objective function. The contribution of this paper is
to provide useful conditions under which an $l_p$-norm objective function is
submodular for all $p\geq 1$, thereby identifying a large class of $l_p$-norm
objective functions that can be minimized via minimal graph cuts.
