A compact representation for minimizers of \(k\)-submodular functions (Q1631630)

The authors establish a compact representation for minimizers of a \(k\) submodular function. This can be viewed as a generalization of the poset representation for submodular functions and Ando-Fujishige's signed poset representation for bisubmodular functions. Minimizers of a \(k\)-submodular function form a median semilattice and, by a Birkhoff-type representation theorem for median semilattices, the minimizer set is represented by a poset with inconsistent pairs (PIP), where minimizers are encoded into special ideals in the PIP, called consistent ideals. PIPs arising from \(k\)-submodular functions are rather special, The authors completely characterize such PIPs and this representation is actually compact. The authors further show that the size of the elementary PIP for a \(k\)-submodular function of \(n\) variables is \(\mathcal{O}(kn)\) and present algorithms to construct the elementary PIP of the minimizers of a \(k\) submodular function \(f\) under the situations: (i) A minimizing oracle of \( f \) is given. (ii) \(f\) is network-representable. (iii) \(f\) arises from a Potts energy function. Furthermore, the authors provide an efficient enumeration algorithm for all maximal minimizers of a Potts \(k\)-submodular function. For a Potts \(k\)-submodular function, the problem of enumerating all maximal minimizers reduces to the problem of enumerating all ideals of a single poset. Experimental results are also presented for real instances.