# Graph Cuts on Markov Random Fields

Binary | Multi-label | |
---|---|---|

Submodular | Exact polynomial-time solution via min-cut/max-flow | Exact polynomial-time solution via min-cut/max-flow |

Metric | N/A | NP-hard, polynomial-time alpha-expansion reaches local-min within a factor of 2 of global min |

Neither | NP-hard, polynomial-time quadratic pseudo-boolean optimization can produce an exact partial solution |
NP-hard, polynomial-time alpha-beta swap reaches local-min |

## Submodularity

Binary submodular cost functions satisfy:

```
Cost(a,b) + Cost(b,a) - Cost(a,a) - Cost(b,b) >= 0
```

Multi-label submodular cost functions satisfy:

```
Cost(b,c) + Cost(a,d) - Cost(b,d) - Cost(a,c) >= 0, where b > a and d > c
```

From a set theory perspective, a cost function is submodular if adding an element x to set S incurs a cost increase α, which is less than or equal to the cost increase β incurred by adding element x to set T, where T is any subset of S. In other words, submodularity implies a diminishing-costs effect.

Convex cost functions (where smoothness is preferred and larger label differences have larger costs) are a common class of submodular costs.

## Metric costs

Metric cost functions satisfy the following criteria:

```
Cost(a,a) = 0
Cost(a,b) > 0
Cost(a,b) = Cost(b,a)
Cost(a,c) <= Cost(a,b) + Cost(b,c)
```