2016/10/01 by Hiroshi Hirai, Hirai, Hiroshi, Taihei Oki +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Digital Image Processing Techniques #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1610.00151
openalex publication_date 2016/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.