# Metadata

- Title: A compact representation for minimizers of k-submodular functions
- Authors: Hiroshi Hirai, Taihei Oki
- Year: 2017
- Venue: arXiv preprint (`arXiv:1610.00151v2`, March 29, 2017); earlier ISCO 2016 version
- Primary group: k-submodular
- Secondary tags: minimization, PIP, median-semilattice, Potts, persistency, network-representable
- Problem: represent and compute the full minimizer structure of k-submodular functions compactly, especially for network-representable and Potts subclasses
- Main guarantee: shows minimizers of a k-submodular function form a median semilattice representable by an elementary poset with inconsistent pairs (PIP) of size `O(kn)`; gives construction from a minimizing oracle in `O(kn^2)` calls, from residual graphs for network-representable functions, and for Potts subclasses in `O(log k)` maxflows; also reduces enumeration of maximal Potts minimizers to ideal enumeration in a poset
- Key techniques: Birkhoff-type representation via PIPs, elementary-PIP characterization, residual-graph extraction, Potts-specific multiflow structure, and maximal-minimizer enumeration
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #minimization #PIP #median-semilattice #Potts #persistency #network-representable #arXiv
- Inbox source: inbox/1610.00151v2.pdf