# Max-cut equivalence with most likely assignment to an Ising model

Ising Model

$$Pr(x; \lambda) = \frac{1}{Z(\lambda)} \exp \left( \sum_{ij \in E} \lambda_{ij} x_{ij} \right)$$

In which $\lambda_{ij} \in \mathbb{R}$, and
$$x_{ij} = \begin{cases} 1 & x_i = x_j\\ -1 & x_i \neq x_j \end{cases}$$

and we are looking for

$$x^* = \arg\max_x Pr(x; \lambda)$$

This is proven to be NP-Complete.

Max Cut

Given the graph $G(V,E)$ and non-negative weights $w_{ij} \in E$ the goal is to find the set of vertices $S$ such that we maximize the the weight of edges in the cut $(S, V \setminus S)$ (the edges with the start-point in $S$ and end-point in $V\setminus S$). More formally, by assuming $w_{ij} = 0, \forall e_{ij} \notin E$, we dote the weight of the cut by $w(S, V \setminus S) = \sum_{i \in S, j \in V \setminus S} w_{i,j}$

This is proven to be NP-Complete.

Min Cut

Exactly like Max-Cut, but the goal is to minimize the weight of the cut.

The problem could be solved in polynomial time using its max-flow formulation.

Problem Statement

In [1] (Page 16, last paragraph) it is mentioned that "finding the most likely assignment in an Ising model is equivalent to a cut problem. For example, if $\mu \leq 0$, then the MAP assignment for graph $G = (V; E)$ corresponds to the maximum cut of $G$ with edge weights $\lambda$."

I am looking for the direct conversion between the two problems. The 2nd sentences (Started by "For example") also doesn't make sense to me.

On the other hand in Page 20 of [1] (Second paragraph), it is mentioned that:

"In the positive side, MAP inference in Ising models with ferromagnetic potentials, or positive edge weights, is equivalent to the minimum cut problem, which can be solved in nearly linear time (Karger, 2000)"

I'd interpret this as, Min Cut (which is Poly-time) is special case of MAP inference. Again, this is a little vague.

In the formulation you give for the Ising model, we are trying to maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise. In maximum cut, we take each edge weight $w$ and try to maximize $\sum_{ij\in E}w_{ij}(-x_{ij})$ -- this is equivalent to maximizing the weight of the cut because the total weight remaining is completely determined by the cut. So we just want to set $w_{ij}=\lambda_{ij}$ to make an equivalent formulation.