  The problem of minimizing the Potts energy function frequently occurs in
computer vision applications. One way to tackle this NP-hard problem was
proposed by Kovtun [19,20]. It identifies a part of an optimal solution by
running $k$ maxflow computations, where $k$ is the number of labels. The number
of "labeled" pixels can be significant in some applications, e.g. 50-93% in our
tests for stereo. We show how to reduce the runtime to $O(\log k)$ maxflow
computations (or one {\em parametric maxflow} computation). Furthermore, the
output of our algorithm allows to speed-up the subsequent alpha expansion for
the unlabeled part, or can be used as it is for time-critical applications.
  To derive our technique, we generalize the algorithm of Felzenszwalb et al.
[7] for {\em Tree Metrics}. We also show a connection to {\em $k$-submodular
functions} from combinatorial optimization, and discuss {\em $k$-submodular
relaxations} for general energy functions.
