# Hirai, Oki 2017 - A compact representation for minimizers of k-submodular functions

## One-paragraph Summary

Neu Huber-Kolmogorov cho ta Min-Max viewpoint cho gia tri toi uu, thi paper nay cho ta cau truc cua ca tap minimizers. Ket qua trung tam la: minimizers cua mot `k`-submodular function tao thanh mot median semilattice, va vi the co the duoc ma hoa bang mot poset with inconsistent pairs (PIP). Trong lop `k`-submodular, PIP nay co dang dac biet goi la elementary PIP, co kich thuoc chi `O(kn)`. Paper sau do khong dung lai o structural theorem: no chi ra cach xay PIP tu minimization oracle, tu residual graph neu ham network-representable, va tu Potts subclass trong cung `O(log k)` maxflows; dong thoi cho enumeration tat ca maximal minimizers cho Potts relaxations.

## Setup

- Objective: khao sat tap `argmin f` voi `f : {0, ..., k}^n -> R`.
- Muc tieu khong chi la tim mot minimizer, ma nen mot representation compact cho toan bo tap minimizers, dac biet de phuc vu partial optimal labeling.

## Main Results

1. Lemma 3:
   moi tap dong duoi `sqcap`, `sqcup` la mot median semilattice.
2. Theorem 7:
   PIP cua tap minimizers cua mot `k`-submodular function la elementary; va nguoc lai, moi elementary PIP tuong ung mot tap `(sqcap, sqcup)`-closed.
3. Proposition 5:
   kich thuoc elementary PIP chi `O(kn)`.
4. Theorem 13:
   neu co minimizing oracle, co the xay elementary PIP bang `O(kn^2)` calls.
5. Theorems 15-17:
   neu ham network-representable, PIP doc ra truc tiep tu residual graph; trong Potts case, xay duoc PIP voi cung do phuc tap `O(log k)` maxflows.
6. Theorem 23 va 26:
   trong Potts subclass, maximal minimizers giam thanh bai toan liet ke ideals cua mot poset don.

## Core Algorithmic Idea

- Dau tien, thay vi lam viec truc tiep voi vectors nhan, paper xem tap minimizers nhu mot cau truc thu tu co phep meet / join cuc bo.
- Birkhoff-type representation cho median semilattices cho phep ma hoa moi minimizer bang mot consistent ideal trong PIP.
- Doi voi `k`-submodular, cac PIP hop le khong phai tuy y ma phai thoa elementary conditions, phan chia thanh tung "part" tuong ung cac bien.
- Trong network-representable cases, residual graph cua maxflow tiet lo quan he thu tu va inconsistent pairs; do do representation co the trich truc tiep tu du lieu flow.

## Proof / Analysis Strategy

- Buoc 1:
  chung minh tap minimizers dong duoi `sqcap`, `sqcup`, nen la median semilattice.
- Buoc 2:
  ap dung correspondence median-semilattice <-> PIP.
- Buoc 3:
  khai thac hinh hoc cuc bo cua `S_k^n` de characterise lop PIP co the xay ra; do la ly do cua elementary conditions.
- Buoc 4:
  cho cac special subclasses, bieu dien minimizers qua residual graphs / multiflow, tu do rut ra PIP ma khong can duyet toan bo minimizer set.

## Why This Matters

- Mot minimizer rieng le chi cho mot partial assignment.
- PIP representation cho thay toan bo khong gian partial optimal labelings va quan he bao ham cua chung.
- Trong vision / Potts applications, dieu nay cho phep liet ke tat ca maximal persistent labelings, khong chi mot cai.

## Key Techniques

- median semilattice
- PIP / consistent ideals
- elementary PIP characterization
- residual-graph extraction
- Potts-specific multiflow structure
- maximal minimizer enumeration

## Delicate Points / Caveats

- Paper can minimization oracle hoac lop ham co structure; no khong bien oracle-model minimization tong quat thanh practical algorithm.
- Representation compact nhung van structural; muon su dung cho mot ung dung cu the can them network or Potts machinery.
- Day la paper "tap minimizers", khong phai maximization.

## Extraction To Concepts

- Nen giu concept moi khong tao qua chi tiet; thay vao do bo sung vao `concepts/k-submodular-relaxation.md` va `concepts/k-submodularity.md` rang minimizers co the duoc ma hoa bang elementary PIP.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them mot nhanh structural:
  `Huber-Kolmogorov -> Hirai-Iwamasa -> Hirai-Oki`,
  trong do paper nay dong vai tro "representation of all minimizers", khac voi Min-Max certificate va relaxability.