A compact representation for minimizers of $k$-submodular functions
  A $k$-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a $k$-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando-Fujishige's signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from $k$-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a $k$-submodular function $f$ for three cases: (i) a minimizing oracle of $f$ is available, (ii) $f$ is network-representable, and (iii) $f$ arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts $k$-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances. 
Hiroshi Hirai and Taihei Oki
math.OC