# Gridchyn, Kolmogorov 2013 - Potts model, parametric maxflow and k-submodular functions

## One-paragraph Summary

Day la paper structural quan trong noi computer-vision Potts energies voi `k`-submodularity. Dong gop truc tiep la tang toc Kovtun preprocessing tu `k` lan maxflow xuong `ceil(1 + log_2 k)` lan maxflow, hoac mot lan parametric maxflow, bang cach dua bai toan ve mot tree-metric labeling problem co unary `T`-convex. O lop y tuong rong hon, paper formal hoa `k`-submodular relaxations cho multilabel energies, chi ra persistency / partial optimality cua cac relaxation nay, va so sanh relaxation Potts tu nhien voi Kovtun preprocessing.

## Setup

- Potts energy tren label set `L`:
  `f(x) = sum_i f_i(x_i) + sum_{ij} lambda_ij [x_i != x_j]`.
- Muc tieu khong phai tim nghiem toi uu toan cuc truc tiep, ma tim mot phan assignment co the co dinh trong mot nghiem toi uu.
- Paper dua bai toan sang ham `g : (L union {o})^V -> R` voi tree metric tren mot star rooted tai `o`.

## Main Results

1. Theorem 4:
   neu `x` toi uu cho ham tree-metric `g`, thi phep chieu `x[ab]` len moi canh `ab` cho ra nghiem toi uu cua binary subproblem tren `{a,b}`; nguoc lai, binary optimum tren mot canh xac dinh duoc mot phan cua mot nghiem toi uu cua `g`.
2. Theorem 5:
   cho divide-and-conquer algorithm giai bai toan tree-metric labeling bang viec tach cay theo mot canh va giai de quy hai bai toan con.
3. Theorem 7:
   coarea formula bieu dien `g(x)` thanh tong cac binary projections `g(x[ab])`, dong thoi cho nesting property giua cac binary minimizers can ke nhau tren cay.
4. Chuyen sang Potts star metric:
   Kovtun preprocessing duoc thuc hien trong `ceil(1 + log_2 k)` maxflow calls, hoac mot parametric maxflow call.
5. Proposition 10:
   moi k-submodular relaxation deu co persistency: nhan nao duoc gan label khac `0` trong nghiem toi uu cua relaxation thi co the giu nguyen trong mot nghiem toi uu cua bai toan goc.

## Core Algorithmic Idea

- Thay vi giai rieng `k` bai toan nhi phan `f_a`, paper xay mot ham `g` tren `L union {o}` ma binary projection cua no tren moi canh `ab` tai tao dung binary bai toan can thiet.
- Chon mot canh `ab` cua cay nhan, giai binary subproblem tren `{a,b}` bang maxflow.
- Binary nghiem nay chia tap dinh thanh hai mien co the fix mot phan nhan, tu do bai toan tach thanh hai bai toan con doc lap tren hai cay con.
- Lap lai de quy cho den khi cay con chi con mot nhan.

## Proof / Analysis Strategy

- Dieu kien `T`-convex cua unary terms thay cho convexity tren chain, du de kiem soat binary projections.
- Theorem 4 la lemmas trung tam: binary optimum tren mot canh co the "lift" thanh mot global optimum cua `g`.
- Theorem 7(a) cho coarea formula, giai thich vi sao thong tin tu tat ca binary projections da du de xac dinh global minimizer.
- Parametric maxflow nesting duoc dung de dong bo cac binary minimizers va thu duoc tinh chat de quy nhat quan.

## Key Techniques

- tree-metric reduction cho Potts preprocessing
- `T`-convex unary functions
- coarea formula tren tree edges
- parametric maxflow nesting
- partial optimality / persistency
- natural k-submodular relaxations cho multilabel energies

## Delicate Points / Caveats

- Paper khong giai quyet polynomial-time oracle minimization cua `k`-submodular functions noi chung; no lam ro mot subclass gan Potts / network flow.
- Tac gia neu ra mot construction "constant outside `[k]^n`" nhu mot relaxation tong quat, nhung Hirai-Iwamasa 2016 sau do chi ra claim ton tai tong quat nhu vay la khong dung neu khong them dieu kien domain.
- Trong Potts case, natural `k`-submodular relaxation cho persistency nhung yeu hon Kovtun preprocessing: neu relaxation label mot dinh thi Kovtun cung label, nhung chieu nguoc lai khong nhat thiet dung.

## Extraction To Concepts

- Nen cap nhat `concepts/k-submodular-relaxation.md` voi:
  - persistency viewpoint;
  - Potts relaxation nhu mot entry point ung dung;
  - distinction giua relaxation tu nhien va preprocessing manh hon.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen them paper nay vao structural / relaxation line ben canh Huber-Kolmogorov.

## Why It Matters

Paper nay dat cau noi giua ba cum se lap lai nhieu lan trong repo:

- Potts / vision partial optimality;
- `k`-submodular relaxations;
- minimizer structure cua cac ham `k`-submodular dac biet.

No la diem vao tu nhien de doc tiep Hirai-Iwamasa 2016 va Hirai-Oki 2017.